icontofig | 发布于 2019-10-31 20:13:52 | 阅读量 311 | 二分 分数规划 树状数组
发布于 2019-10-31 20:13:52 | 二分 分数规划 树状数组

题目大意

给出一些线段,给出这些线段的起始和终止位置,并给出这些线段选取的两个代价A和B,要求选取一些线段覆盖区间[1----t],使得ΣAi与ΣBi的比值最小。

题解

很经典的01分数规划问题的形式。

当天训练的时候就想到了BUPT2019校赛的一道01分数规划问题,当时还是我们队拿的那题一血,可惜当时的队友现在因为一些原因分开了,真是令人感叹,sigh。

回归正题……

这一类最经典的01分数规划的解题基本思路是十分固定的,如下:

1.二分一个目标值mid

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

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

那么我们如何去构造这样一组可行解呢?

我们将不等式换一下形式,换成没有分式的不等式形式:mid * ΣBi - ΣAi >= 0;

这样我们就需要构造一组线段选取方案去满足上面的那个等式。

为了使得选取的区间完整,我们可以先将区间按照左端点为第一关键字,右端点为第二关键字从小到大进行排序,这样会保证在能构造出一组当前mid值条件下的可行解的时候我们不会漏掉中间的一部分区间。

之后我们先将所有mid * Bi - Ai >= 0的所有区间都选中,并统计加和sum,因为这些区间会使得不等式左边尽可能大。如果这时候已经能够覆盖所有需要覆盖的区间,那么就说明这样就已经能达到一组可行解了。

如果还没有覆盖所有区间,那么我们就要在剩下没有选中的线段中选取一些线段使得他们的ΣAi - mid * ΣBi尽可能小,这样不等式才能尽可能成立。

如何尽可能小?这时候我们可以使用树状数组去统计当前线段起点S前一个位置S-1到t的最小值(这里树状数组需要维护当前点到t的最小代价值),然后将选这个线段的方案统计入树状数组去求最小值。

之后我们去查询到t的最小值,判断sum是否大于等于 query(t)。如果sum >= query(t),则满足上述不等式,二分区间向左缩进。否则将二分区间向右缩进。

为了保证二分精度,我们可以限定二分次数,而非用eps判定二分区间端点l与r的关系。具体实现见代码吧。

代码

#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;
}



内容更新于: 2019-10-31 20:14:00
链接地址: http://blog.leanote.com/post/icontofig/CCPC2017%E5%93%88%E5%B0%94%E6%BB%A8%E7%AB%99-Server%E2%80%94%E2%80%9401%E5%88%86%E6%95%B0%E8%A7%84%E5%88%92

上一篇: BZOJ 2242 SDOI2011 计算器

下一篇: HAOI2018 染色 NTT 组合数 生成函数

311 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航