P14636 [NOIP2025] 清仓甩卖 题解

合法的方案数并不好求，因此考虑正难则反，计算不合法的方案数。

首先尝试刻画一下不合法的条件。显然，如果小 R 购买的糖果是按照性价比排序后的一段前缀，则他买到的糖果一定是最优的；因此，我们只需要考虑中间有一些糖果因为买不起而没有买的情况。设：

则小 R 会先购买糖果 $y$，再购买若干满足 $w_i=2$ 的糖果，并在只剩下恰好一元钱时遇到糖果 $x$；由于小 R 买不起糖果 $x$，他只能被迫购买糖果 $z$。
显然，当 $a_x \gt a_y+a_z$ 时，购买糖果 $x$ 是比购买糖果 $y$ 和糖果 $z$ 更优的，这种定价方案并不能使小 R 买到的糖果的原价总和最大。于是，我们只需要计算满足 $a_x \gt a_y+a_z$ 的方案数即可。

我们将所有糖果按照原价从大到小排序，并将此时的下标作为糖果的编号。考虑枚举 $x$ 和 $y$（$a_x \gt a_y \gt \dfrac{a_x}2$），设 $u$ 为最大的满足 $a_u \gt \dfrac {a_x} 2$ 的正整数，$v$ 为最大的满足 $a_v \ge a_x-a_y$ 的正整数，则有下面的要求：

同时，设 $[1,x-1]$ 中满足 $w_i=2$ 的 $i$ 有 $f$ 个，$[x+1,y-1]$ 中满足 $w_i=1$ 的 $i$ 有 $g$ 个，为了使遇到糖果 $x$ 时剩下恰好一元钱，需要满足 $x-1+f+g+1=m-1$（加 $1$ 是因为还要买糖果 $y$）。

对于 $x$ 前面的糖果，相当于要从 $y-2$ 颗糖果里选 $m-x-1$ 颗，让它们的贡献加 $1$，一共有 ${y-2} \choose {m-x-1}$ 种方案；对于 $x$ 后面的糖果，$[v+1,n]$ 中的每颗糖果都有两种方案，方案数为 $2^{n-v}$；将两部分相乘，可以得到此时的方案数为 ${{y-2} \choose {m-x-1}} \cdot 2^{n-v}$。

于是我们只需要枚举 $x$ 和 $y$，利用双指针求出 $v$ 的值，计算出方案数并相加即可。

时间复杂度 $\mathcal O(\sum n^2)$。