题解：P14636 [NOIP2025] 清仓甩卖 / sale（民间数据）

· · 题解

upd：修改了一处笔误。

注：本题解中的大小关系，前后顺序都是以性价比降序排序为基准。

考场上没调出来。倒闭。

正难则反。我们会发现不合法的情况一定是前面的一个 1 卡住了后面的一个 2。设 2 的位置是 i，那个 1 的取值范围就是 a_i 到 \frac{a_i}{2}，于是可以在这个范围里枚举 j（那个 1 的位置）。

注意到不合法的情况一定是后面不存在一个 1（设它的位置是 k）满足 a_j + a_k \ge a_i，于是 a_j 到 a_i - a_j 范围里的数的 w 必须是 2，而 a_i - a_j 到 1 范围里 1 和 2 都行。

然后因为卡住的原因一定是因为遇到这个 i 时的金币数只有 1 了。所以可以推得 \sum_{p>j}w = m-2，于是问题变为使性价比最大的 j - 1 个数的 w 的和为 m-2。

设 x 为 1 到 a_i - 1 中有多少个 2，nxt 为后面第一个可以填 1 的位置（可以用双指针维护），利用范德蒙德卷积可推得：

ans = \sum \binom{i - 1}{x}\binom{j - i}{m - 2 - (i -1) - x} \times 2^{n - nxt +1} = 2^{n - nxt + 1} \binom{j - 1}{m - i - 1}

只需枚举 i, j，并用双指针维护 nxt，所以复杂度是 n^2 的。

最后，注意我们求得是反面，需要的是正面。