19.10.18

题目描述

nn 个物品,第 ii 个物品有两个属性 kik_ibib_i ,表示它在时刻 xx 的价值为 ki×x+bik_i\times x + b_i

当前处于时刻 00 ,你可以选择不超过 mm 个物品,使得存在某个整数时刻 ttt0t \geq 0 ,你选择的 所有物品的总价值大于等于 SS

给出 SS ,求 tt 的最小值。

n105n\leq10^5

核心思路

题目显然就是

(kx+b)=kx+b>s\sum(kx+b)=\sum kx+\sum b>s

这个式子非常难维护。

考虑是否具有单调性,显然,这个必然是先减后增的。直接二分答案。

考虑如何二分答案,只需要先检查 00 的位置是否合法,就可以直接忽略掉递减的部分了。

考虑如何check,题目规模要求 Θ(n)\Theta(n) 地检查。这里有一个玄学操作nth_element,复杂度玄学,可以卡过随机数据。

考试的时候没想清楚这一点,想着有一定的概率二分可以过。然后看到题目有一个subtask是 i,ki<0\forall i,k_i<0 ,就自己特判了一下 00 的情况,就比别人多了12分。

代码略


 评论