自动搬运

查看原文

来自洛谷，原作者为

	__stick To the time to life,rather than to life in time

搬运于2025-08-24 21:25:42，当前版本为作者最后更新于2022-06-05 18:20:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题意

$n$ 个梨子，每个梨子有两个参数 $a_{i},b_{i}$ ，给出三个参数 $c_{1},c_{2},c_{3}$ ，选择若干个梨子使得对于选择的每个梨子 $i$ 都满足

$$c_{1} (a_{i}-a_{0})+c_{2} (b_{i}-b_{0}) \le c_{3} $$

其中 $a_{0},b_{0}$ 是所有选择的梨子中的最小的 $a /\ b$。

想法

这里提供一个 $\ O( n^{2} \log n \ )$ 的做法，不是很优秀，但是好想。

首先是将公式移项，讲已知的放到一边，得：

$$c_{1} \times a_{i}+c_{2}\times b_{i} \le c_{3}+c_{2} \times b_{0}+c_{1} \times a_{0} $$

这样的话我们会发现只要所选出的 $\ a_{i},b_{i} \$ 的最小值确定了，右边就是一个常数，为叙述方便记这个数为 $k$。问题也就变成了求给出题目中满足小于某定值的数的个数，所以我们考虑 枚举最小值 $a_{0},b_{0}$ ，再去一一检查数列中满足 $a_{i} \ge a_{0} \wedge b_{i} \ge b_{0} \wedge c_{1}\times a_{i}+c_{2}\times b_{i} \le k $ 的数的个数，复杂度显然是 $O(n^{3})$ ，不能接受，考虑优化。

首先优化枚举的复杂度，由于不关心顺序，我们完全可以排序，我们先按 $a$ 从小到大排序，再依次枚举，就确定了 $a_{0}$， 那 $b_{0}$ 怎么办呢？我们会发现，其实我们关心的只是最小值，其他的都不会影响答案，所以我们可以骚气的对枚举到的 $a_{0}$ 后边的数组以 $b$ 为关键字进行降序排序，就又保证了 $b_{0}$ 的有序性，这样复杂度就能降下来了，为什么呐？

我们想一下，既然我们已经确定了 $a_{0}$ ，那 $\ k\$ 其实就是一个关于 $\ b_{0}$ 的一次函数，如果 $\ b_{0}\$ 单调递减，那么 $k$ 也是单调递减的，那我们就能利用这个性质，如果一个梨子 $i$ 所算出来的值已经大于当前的 $k$ 那它在枚举下一个 $b_{0}$ 时一定也会大于所计算出来的 $k$（因为 $k$ 单调减）我们直接舍弃，所以我们用大根堆维护选择的梨子 枚举 $b_{0}$ 时讲当前题目的值压入堆，再弹出不合法的值，最后就是可选择的题目了，复杂度明显是 $\ O(n^{2} \operatorname{log}n)$，$n=2000$ 完全能过 （吸氧才能过）。

代码