icontofig | 发布于 2019-10-31 20:13:52 | 阅读量 317 | 二分 分数规划 树状数组
发布于 2019-10-31 20:13:52 | 二分 分数规划 树状数组
CCPC2017哈尔滨站 Server——01分数规划+树状数组
题目大意给出一些线段,给出这些线段的起始和终止位置,并给出这些线段选取的两个代价A和B,要求选取一些线段覆盖区间[1----t],使得ΣAi与ΣBi的比值最小。 题解很经典的01分数规划问题的形式。 当天训练的时候就想到了BUPT2019校赛的一道01分数规划问题,当时还是我们队拿的那题一血,可惜当时的队友现在因为一些原因分开了,真是令人感叹,sigh。 回归正题…… 这一类最经典的01分数规划的解题基本思路是十分固定的,如下: 1.二分一个目标值mid 2.贪心地去构造检验是否有一组可行解,使得ΣAi / ΣBi <= mid; 3.如果能构造出这样一组可行解,那么将二分区间向左缩进,
继续阅读