class="markdown_views prism-atom-one-light"> 这个是CCPC哈尔滨的K题，当时听到隔壁THU卡题少女队说是01分数规划，没学过就弃了。后来发现这玩意挺傻逼的，今天掏出来BB了一顿很快就AC了。
题意: 从一堆[si,ti]的区间中选一部分完全覆盖[1, T], 每个区间有两个权值ai bi, 要求选用的区间的 ∑ai∑bi 的最小值。
做法: 先参考一下fjzzq大佬的文章https://www.cnblogs.com/zzqsblog/p/5450361.html , 发现01分数规划就是二分答案之后把分母乘上去，使得 ∑ai−bi∗mid 为正(负), 这个只要把 ai−bi∗mid 作为新的权值从大往小贪一下即可。然后在这个题里面，二分答案之后，显然正的部分全部要取完，这样就变成了如何用最少的代价覆盖剩下的区间，这个我把线段按左端点排序之后用bit维护dp就做完了。这样复杂度有两个log, 但是考虑到时限给了10s, 还是很轻松就AC了, 耗时2652ms。
代码: #include using namespace std; const int maxn=100007; int n, t; struct node { int s, t, a, b; bool tag; }rec[maxn]; bool cmp(node a, node b){ if(a.s==b.s)return a.treturn a.sbool vis[maxn]; double c[maxn]; int lowbit(int x){ return x&(-x); } void update(int x, double num){ while(x){ c[x]=min(c[x], num); x-=lowbit(x); } } double query(int x){ if(x==0)return 0; double ans=1e9; while(x<=t){ ans=min(ans, c[x]); x+=lowbit(x); } return ans; } bool check(double mid){ double sum=0; int r=0; for(int i=1;i<=t;i++){ c[i]=1e9; } for(int i=1;i<=n;i++){ if(rec[i].b*mid-rec[i].a>0){ sum+=rec[i].b*mid-rec[i].a; rec[i].tag=true; if(rec[i].s-1<=r){ r=max(r, rec[i].t); } } else rec[i].tag=false; } if(r==t)return true; update(r, 0); for(int i=1;i<=n;i++){ if(!rec[i].tag){ double from=query(rec[i].s-1); update(rec[i].t, from+rec[i].a-rec[i].b*mid); } else { double from=query(rec[i].s-1); update(rec[i].t, from); } } return sum>=query(t); } int main(){ int T; scanf("%d", &T); while(T--){ scanf("%d%d", &n, &t); for(int i=1;i<=n;i++){ scanf("%d%d%d%d", &rec[i].s, &rec[i].t, &rec[i].a, &rec[i].b); } sort(rec+1, rec+1+n, cmp); double l=0, r=1001; int tim=30; for(int i=1;i<=tim;i++){ double mid=(l+r)/2; if(check(mid))r=mid; else l=mid; } printf("%.3f ", l); } }