题解：P14636 [NOIP2025] 清仓甩卖 / sale

solution

• 若 $w_i=1$，性价比为 $a_i$。
• 若 $w_i=2$，性价比为 $\dfrac{a_i}{2}$。

• 贪心过程中，因为剩余钱数为 $1$，跳过了一个性价比很高但买不起的 $2$ 元糖果 $u$。
• 随后，用这 $1$ 元钱买了一个 $1$ 元糖果 $v$（或者没买任何东西，即 $v$ 不存在，$a_v=0$）。
• 如果此时，在已经购买的 $1$ 元糖果集合中，存在一个糖果 $z$，满足 $a_u > a_z + a_v$（即把 $z$ 和 $v$ 换成 $u$ 会更优），那么贪心策略就失败了。

• 集合 $A$ ($i < u$)：$a_i \ge a_u$：
  • 无论 $w_i$ 是 1 还是 2，其性价比都 $\ge \dfrac{a_u}{2}$。这些糖果一定在 $u$ 之前被考虑。
• 集合 $B$ ($i > u$ 且 $2a_i > a_u$)：$a_i > \dfrac{a_u}{2}$。
  • 若 $w_i=1$，性价比 $a_i > \dfrac{a_u}{2}$，在 $u$ 之前考虑（被购买）。
  • 若 $w_i=2$，性价比 $\dfrac{a_i}{2} < \dfrac{a_u}{2}$，在 $u$ 之后考虑。
• 集合 $C$ ($i > u$ 且 $2a_i \le a_u$)：
  • 无论 $w_i$ 是 1 还是 2，性价比都 $\le \dfrac{a_u}{2}$，一定在 $u$ 之后考虑。

• 如果是 $w=2$，买不起，跳过。
• 遇到的第一个 $w=1$ 的糖果即为 $v$。
• 如果遍历完 $C$ 也没遇到 $w=1$，则 $v$ 不存在。

• $A \cap S$ 中的元素必须是 $2$ $\Rightarrow$ $k_A$ 增加 $|A \cap S|$。
• $B \cap S$ 中的元素必须是 2 $\Rightarrow$ $k_B$ 不增加（因为 $k_B$ 统计的是 $w=1$）。