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

初中生第一次场切紫题，来记录一下。

先考虑 $m=2$ 时怎么做。
设一个代价为 $2$，价值为 $B$，和两个代价为 $1$，价值为 $A, C$，当 $C>\dfrac B2$ 且 $A+C<B$ 时不合法。
在这里，这个 $B$ 为最大值，答案很容易统计。

考虑推广，我们先枚举 $j$，对应上述中 $B$ 的下标。
那么性价比可能比 $B$ 大的 $i$ 满足 $a_i > \dfrac{a_j}2$。
设最小的 $i$ 为 $d$，为了满足条件， $[d,j-1]$ 的 $w$ 为 $1$，$[j+1,n]$ 的 $1,2$ 均可。
为了统计 $A+C<B$ 的数量，我们枚举 $C$ 的下标 $k$，$a_i$ 在 $[a_j-a_k,\infty)$ 代价只能是 $2$，$[0, a_j-a_k)$ 则随便（可以排序后双指针维护）。
而 $[k+1, j-1], [j+1, n]$ 部分的点的代价要凑成 $m-2$，有 $\binom{n-k-1}{2(n-j)+(j-k)-m+1}$ 种，要注意 $a_k$ 不能等于 $a_j$。