自动搬运

查看原文

来自洛谷，原作者为

	Exp10re My awAKen Dream.

搬运于2025-08-24 23:05:54，当前版本为作者最后更新于2024-11-15 17:28:39，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

做法来自

给一种证明部分完全与反悔无关的做法，会比反悔思路简单很多。

解题思路

考虑如下做法：

• 添加 $n$ 张限制为 $a_i$，优惠为 $a_i-b_i$ 的虚空优惠券。
• 然后仅考虑 $n$ 件商品的原价以及这 $n+m$ 张优惠券，用它们进行朴素贪心 $^\dagger$，得到的答案即为本题的答案。

$\dagger$：参考 ABC308F，将物品以及优惠券排序后从小到大枚举物品，然后将满足限制的优惠券加到大根堆中贪心的使用最大的优惠券。

我们考虑为什么这么做是对的：容易发现这么做唯一的问题在于可能有一个原价不为 $a_i$ 的商品 $a_j$ 使用了 $a_i$ 产生的虚空优惠券，根据贪心这个时候 $a_i$ 会使用另一张优惠券减 $x$ 元，记这一张优惠券的限制为 $lim$。

可以发现 $a_j$ 会抢走 $a_i$ 的虚空优惠券的一个必要条件是 $a_j\geq a_i$，又有 $lim\leq a_i \leq a_j$，故此时交换 $a_i$ 与 $a_j$ 的优惠券可以使得 $a_i$ 使用自己产生的虚空优惠券，即使用原先的 $b_i$ 折扣，并且不会产生任何额外代价。

故经过若干次交换可以使得每一个商品使用原先给出的优惠券以及自己的虚空优惠券，并且在此限制条件下不会产生比朴素贪心更高的代价，故正确性得证。

时间复杂度 $O(n\log (n+m))$。