solution

· · 题解

题意

$$ 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$ 完全能过 ~~（吸氧才能过）~~。 [代码](https://www.luogu.com.cn/paste/i1rp1oha)