HDU6240-二分+分数规划

题目链接

HDU6240

题目大意

给出n个区间和一个长度l，每个区间有一个a，b。
求出能够使得区间全覆盖的同时使得Ans最小，Ans定义如下

$$Ans = \frac{\sum_{i=1}^k a_i}{\sum_{i=1}^kb_i}$$

思路

没学过分数规划，重新学了一遍,重新看一遍这个式子

$$\frac{\sum_{i=1}^k a_i \times x_i}{\sum_{i=1}^kb_i \times x_i}$$

其中$x_i$是0或1，即x是一个0和1组成的集合，代表选和不选。我们二分一个mid就可以求出最大值和最小值，如下。

$$\begin{aligned} &\frac{\sum_{i=1}^k a_i \times x_i}{\sum_{i=1}^kb_i \times x_i} > mid\\ \to&\sum_{i=1}^ka_i\times x_i - mid*{\sum_{i=1}^kb_i \times x_i} > 0\\ \to&\sum_{i=1}^kx_i*(a_i-mid\times b_i)>0 \end{aligned}$$

得到mid之后只需要判断左边那个是否大于0即可。如果要求选k个，肯定选前k个最大的。
回到这题，一样采用二分的方法，二分出来值后，如果$a_i - mid*b_i>0$，说明这条边对当前答案mid是正影响，即加进来只会使得整个值大于mid，把这样的边全都加进去，然后考虑区间覆盖的问题，剩下的负影响的我们要使得它的影响最小，最后比较正影响和负影响的值即可。区间覆盖的问题可以用树状数组来解决，枚举每个线段，然后查找l-1的负影响的最小值，判断当前边是正影响还是负影响，正影响不用管，直接更新树状数组r = l-1，如果是负影响就加上这个影响再把(l-1)+{负影响}加到r这个点上。
树状数组维护前缀最小值的更新和求和更新是反过来的。

代码实现

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N =   1e5+10;
double eps = 1e-4;
double tree[N<<2];
int n,t;
int lowbit(int x){
    return x&(-x);
}
void update(int x,double k){
    while(x){
        tree[x] = min(tree[x],k);
        x-=lowbit(x);
    }
}
double query(int x){
    if(x==0)return 0;
    double res = 1e9+7;
    while(x<=t){
        res = min(res,tree[x]);
        x+=lowbit(x);
    }
    return res;
}
struct node{
    int l,r,a,b;
    bool operator <(const node a)const{
        return l<a.l;
    }
    bool judge(double x){
        return a*1.0/b<x;
    }
}line[N];
bool check(double mid){
    double res = 0;
    for(int i=1;i<=t;i++){
        tree[i]=1e9+10;
    }
    for(int i=1;i<=n;i++){
        if(line[i].judge(mid))res+=mid * line[i].b - line[i].a;
    }
    for(int i=1;i<=n;i++){
        double now = query(line[i].l - 1);
        if(!line[i].judge(mid))now+= line[i].a- mid * line[i].b;
        update(line[i].r, now);
    }
    return res>=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", &line[i].l, &line[i].r, &line[i].a, &line[i].b);
        }
        sort(line + 1, line + 1 + n);
        double l = 0, r = 1001;
        for(int i=1;i<=25;i++){
            double mid = (l+r)/2;
            if(check(mid))r = mid;
            else l = mid;
        }
        printf("%.3lf\n",r);
    }
}