# CCPC2017哈尔滨站 Server——01分数规划+树状数组

## 题解

1.二分一个目标值mid

2.贪心地去构造检验是否有一组可行解，使得ΣAi / ΣBi <= mid;

3.如果能构造出这样一组可行解，那么将二分区间向左缩进，否则将二分区间向右缩进。

## 代码

```#include <bits/stdc++.h>
using namespace std;
int n,t;
int T;
const int maxn = 1e5+5;
struct interv{
int s,t,a,b;
}tv[maxn];
double c[maxn];
int flag[maxn];
inline int lowbit(int x){
return x & -x;
}
void update(int pos,double val){
while(pos > 0){
c[pos] = min(c[pos],val);
pos -= lowbit(pos);
}
return;
}
double query(int pos){
if(pos == 0)return 0;
double ans = 1e9;
while(pos <= t){
ans = min(ans,c[pos]);
pos += lowbit(pos);
}
return ans;
}
const double eps = 1e-9;
bool check(double x){
double sum = 0;
int now = 0;
for(int i = 1;i <= t;++i)
c[i] = 1e9;
for(int i = 1;i <= n;++i){
flag[i] = 0;
if(tv[i].b * x - tv[i].a >= 0){
sum += tv[i].b * x - tv[i].a;
flag[i] = 1;
if(tv[i].s - 1 <= now){
now = max(now,tv[i].t);
}
}
}
if(now == t)return true;
update(now,0);
for(int i = 1;i <= n;++i){
if(!flag[i]){
double to = query(tv[i].s - 1);
update(tv[i].t,to + tv[i].a - tv[i].b * x);
}
else{
double to = query(tv[i].s - 1);
update(tv[i].t,to);
}
}
return sum - query(t) >= eps;
}
bool cmp(interv x,interv y){
return (x.s == y.s) ? (x.t < y.t) : (x.s < y.s);
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%d %d",&n,&t);
for(int i = 1;i <= n;++i){
scanf("%d %d %d %d",&tv[i].s,&tv[i].t,&tv[i].a,&tv[i].b);
}
sort(tv+1,tv+n+1,cmp);
double l = 0,r = 1000;
int cnt = 101;
while(cnt--){
double mid = (l + r) / 2;
if(check(mid))
r = mid;
else l = mid;
}
printf("%.3lf\n",l);
}
return 0;
}```