「YLLOI-R1-T2」圣诞星 的题解

· · 题解

因为不管买哪个商品都会让其他的价格减 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)。

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