Tag-分数规划

Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)

 2019-10-31 20:13:52 |  0 Comments  |  二分 分数规划 树状数组

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

题目大意

给出一些线段,给出这些线段的起始和终止位置,并给出这些线段选取的两个代价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 
Title - Artist
0:00