题解：P14636 [NOIP2025] 清仓甩卖 / sale

xcxxx_ · 2025-11-29 15:40:12 · 题解

看到难度是黑还以为自己场切黑题了赶紧来写题解结果还没写完就降紫了/fn

先考虑怎么样设置清仓价会导致小 R 无法获得最大价值。

如果没有任何一颗糖果被跳过，买的就是性价比最大的那些糖果，显然一定可以获得最大价值。

如果有糖果被跳过了，那么这肯定是一颗 w_i=2 的糖果，且小 R 考虑到这颗糖果时刚好只剩一块钱，此时要想要获得一个更优解唯一的方法只有放弃掉之前最后一个被考虑的即原价最低的 w_i=1 的糖果并换成当前的这块糖果。

于是先枚举这两块糖果，设为糖果 i,j 且 w_i=1,w_j=2，由于糖果 i 比糖果 j 先考虑到即性价比更高，那么一定有 a_i>2a_j。

接下来考虑计算钦定了这两块糖果之后剩下的糖果有多少种设置剩下的清仓价的方法可以使小 R 取不到最优解，有如下的限制：

• 更改后可以获得更优解。若是存在一个原价比糖果 i 低的糖果 k 且满足 a_i+a_k\ge a_j，那么就无法更换得到更优解，因此所有原价在 [a_j-a_i,a_i] 间的非糖果 i 的糖的清仓价都必须设为 2，而原价小于 a_j-a_i 的糖的无论清仓价是多少都不会有影响。

• 小 R 考虑到糖果 j 时恰好只剩 1 块钱。也就是说所有性价比高于糖果 j 的清仓价之和恰好为 m-1，而所有性价比有可能高于糖果 j 的糖即为：

  • 所有原价高于糖果 j 的糖，清仓价为 1 或 2 均可。
  • 原价低于糖果 j 但高于糖果 i 的糖，这类糖的原价一定超过糖果 j 的一半，因此只要清仓价为 1 那么性价比就会大于糖果 i。
  • 糖果 i，清仓价为 1。

  第一类糖中的每一个都可能会花费 1 或 2 块钱，第二类糖中的每个都将花费 1 块钱。设第一类糖有 y 个，第二类糖有 x 个，枚举第二类糖中有 k 个清仓价为 1，由总价值为 m-2 可解得第二类糖中清仓价为 2 的有 m-2-k-y 个，则方案数为 \sum\limits_{k=0}^{x}\binom{x}{k}\binom{y}{m-2-k-y}，由范德蒙德卷积得其即为 \binom{x+y}{m-2-y}。

可以发现这样就考虑完了所有糖果，这样就算出来了小 R 取不到最优解的情况，用 2^n 减去即可。

实现方面，将所有糖果按原价排序后枚举 i,j，第一条限制的左端点是递增的因此维护一个指针在序列上滑动即可，复杂度 O(n^2)