【CSP模拟】merchant 题解

19.10.18

题目描述

有 $n$ 个物品，第 $i$ 个物品有两个属性 $k_i$ ， $b_i$ ，表示它在时刻 $x$ 的价值为 $k_i\times x + b_i$ 。

当前处于时刻 $0$ ，你可以选择不超过 $m$ 个物品，使得存在某个整数时刻 $t$ ， $t \geq 0$ ，你选择的所有物品的总价值大于等于 $S$ 。

给出 $S$ ，求 $t$ 的最小值。

$n\leq10^5$

题目显然就是

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

这个式子非常难维护。

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

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

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

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

代码略