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

fush · 2025-11-29 17:15:04 · 题解

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

先考虑 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。