HDU 6240 2017中国大学生程序设计竞赛 哈尔滨站

题意

n个线段，覆盖一段区间，附带有两个属性 $A_i,B_i$Ai​,Bi​
要求，选出一个线段集合，使得覆盖 $[1,t]$[1,t] 并且 $\frac{\sum A_i}{\sum B_i}$∑Bi​∑Ai​​ 最小

题解

01分数规划
二分答案
设二分的答案为 $x$x
将属性变为 $A_i-x\ast B_i$Ai​−x∗Bi​ 的形式
题目要求是最小值
易知，当 $x$x 很大使， $\sum A_i-x\ast B_i\&lt;=0$∑Ai​−x∗Bi​<=0
所以，当存在一种合法方案且使得 $\sum A_i-x\ast B_i\&lt;=0$∑Ai​−x∗Bi​<=0 时，意味着 $x$x 可以缩小，反之， $x$x 需要变大
即 $\sum A_i-x\ast B_i$∑Ai​−x∗Bi​ 的最小值要小于 0
所有的线段分为两类 ： $A_i-x\ast B_i\&lt;=0$Ai​−x∗Bi​<=0 的肯定要选，其余的要选最小的使得能覆盖区间

$dp$dp转移
先按左端点排序， $dp\left[i\right]$dp[i]表示以 $i$i 为结尾，前面都覆盖的最小花费
设枚举的线段为 $[L_i,R_i]$[Li​,Ri​]
可以从 $dp\left[j\right](L_i-1\&lt;=j\&lt;=t)$dp[j](Li​−1<=j<=t) 的最小值转移过来
然后更新 $dp\left[R_i\right]$dp[Ri​]
单点修改，区间最小值，用树状数组可以实现

值得注意的是，只转移 $A_i-x\ast B_i\&gt;0$Ai​−x∗Bi​>0 的线段，肯定要选的当做为 0 来转移

代码

#include<bits/stdc++.h>
#define N 100010
#define INF 0x3f3f3f3f
#define eps 1e-5
#define pi 3.141592653589793
#define mod 1000000007
#define P 1000000007
#define LL long long
#define pb push_back
#define fi first
#define se second
#define cl clear
#define si size
#define lb lower_bound
#define ub upper_bound
#define bug(x) cerr<<#x<<" : "<<x<<endl
#define mem(x,y) memset(x,0,sizeof(int)*(y+3))
#define sc(x) scanf("%d",&x)
#define scc(x,y) scanf("%d%d",&x,&y)
#define sccc(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;
struct node{
    int a,b,l,r;
    bool operator < (const node z) const{
        return l<z.l;
    }
}w[N];
int n,m;
double d[N];
void update(int x,double y){
    for(;x;x-=x&-x) d[x]=min(d[x],y);
}
double sum(int x){
    if (x==0) return 0;
    double res=1e12;
    for(;x<=m;x+=x&-x)  res=min(res,d[x]);
    return res;
}
bool ok(double x){
    double res=0;
    for(int i=1;i<=m;i++) d[i]=1e12;
    for(int i=1;i<=n;i++){
        double t=sum(w[i].l-1);
        double tm=1.0*w[i].a-x*w[i].b;
        if (tm<=0) res-=tm,tm=0;
        update(w[i].r,t+tm);
    }
    return sum(m)<=res;
}
int main(int argc, char const *argv[]){
    int T; sc(T);
    while(T--){
        scc(n,m);
        for(int i=1;i<=n;i++) scc(w[i].l,w[i].r),scc(w[i].a,w[i].b);
        sort(w+1,w+n+1);
        double l=0,r=100001;
        while(r-l>1e-5){
            double mid=(l+r)*0.5;
            if (ok(mid)) r=mid;else l=mid;
        }
        printf("%.3f\n",r);
    }    
    return 0;
}