自动搬运

查看原文

来自洛谷，原作者为

	lovelish 呜呜呜我不管宝宝就要装可爱qwq

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

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

以下是正文

因为不管买哪个商品都会让其他的价格减 $1$，但先买贵的容易让便宜的降为 $0$ 元，使其浪费优惠。因此按照价格从小到大购买一定最优。

现在我们已经确定了这些商品的购买顺序（之后的 a[i] 便是排序后的），那么对于商品购买的优惠券的优惠就已经确定，我们可以先把每个商品先计算出优惠后的价格。第 $i$ 个商品会被买前 $i-1$ 个商品的优惠券优惠，即 a[i]=a[i]-i+1。

接下来我们就只需要考虑一开始买多少张优惠券最优即可。只要一张优惠券能优惠的钱数大于 $w$，这张优惠券就是值的，那么当价格非 $0$ 的商品不超过 $w$ 时，再买优惠券就不会值了，此时停止购买。

如何求出购买多少张优惠券后价格非 $0$ 的商品会不超过 $w$ 个呢？这里有两种求法。

若购买 $x$ 张价格非 $0$ 的商品会超过 $w$ 个，则购买 $x-1$ 张价格非 $0$ 的商品也一定会超过 $w$ 个，可以发现这是有单调性的，因此我们可以直接二分优惠券数，求出价格非 $0$ 的商品超过 $w$ 个的最大优惠券数即可，总时间复杂度 $\mathcal O(n\log W)$，其中 $W$ 为 $a_i$ 的值域（因为当 $w=1$ 时一直买优惠券直到只剩一个价格非 $0$ 的商品是最优的）。

再看另一种求法，因为最后剩下的价格非 $0$ 的商品一定是价格最高的若干个，所以我们可以直接再次排序，求出价格第 $n-w+1$ 高的价格，那么购买这么多优惠券时每张优惠券一定都是值的，并且再多买一张就不是值的了，总时间复杂度 $\mathcal O(n\log n)$。

求出购买多少张优惠券后，模拟一遍统计答案即可。