P14636 题解

你说的对，但是我场上 小时读假题 小时调立方代码还没调出来给我整不知所措然后被清空精神条了导致我赛后对所有不支持评黑的人哈气。

然后躺床上 eps 秒之后精神值恢复了一点突然想到了做法。

首先你考虑最优解和根据题意得到的解的差别在哪。

考虑通过替换掉一些糖果来达到最优解，有以下几种可能：

• 元的糖果换 元的糖果：显然不可能，因为你是按照性价比选择的。
• 元的糖果换 元的糖果：显然不可能，原因同上。
• 一个 元的糖果换 个 元的糖果：根据题意，两元糖果性价比要大于两个 元糖果。因此也不可能更优。
• 两个 元糖果换两个 元糖果：这是唯一有可能的方式。

考虑什么情况下会出现这种情况。将两个一元糖果记作 ，两元糖果记作 。

显然有 。

考虑将原数组排序后枚举 和 ，用双指针确定 的范围统计答案。假设当前确定的区间是 ， 的下标是 。

我们希望前面的代价之和是 ，其中 是一个非负整数。这样我们在加入 的时候就会把区间内的 元糖果顶出去。

注意到，对于 之前的糖果，要么造成 的贡献（定价 元），要么造成 的贡献（定价 元）。对于 及以后的糖果，要么造成 的贡献，要么造成 的贡献（定价 元因为性价比过低没有被选上）。

考虑令所有元素都是其价格更低的那一档，然后从中选几个 使其恰好到 ，这部分可以使用组合数计算。对于 ，使用前缀和即可。注意需要减去区间内元素全定价一元的情况。

但是有个问题：如果前面的元素恰好凑成了 ，连 都放不下怎么办？看上去似乎没法做了（哈哈，我考场上就是这么想的，然后打暴力去了）。

在床上躺了 eps 秒之后我想到了这个方法。

考虑如何计算不算区间内 元糖果的代价之和。此时 区间内要么造成 的贡献，要么造成 的贡献（被挤出去），凑成了 的代价。仿照上面的方法进行前缀和即可（其实也是场上的旧思路，以为假了就没管了）。

需要注意，如果此时区间内一个 元糖果都没有并且凑成了 ，会被上面的方法减掉 次，需要加回来，算是一个小容斥。

然后经过巨量卡常即可通过。复杂度 。