题解：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$ 的位置（可以用双指针维护），利用范德蒙德卷积可推得：

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

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