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

无名之雾 · 2025-11-29 16:30:00 · 题解

感觉不是很难啊。可能是我比较擅长这种东西吧。

随机写了一下通过了大样例。目前能通过洛谷数据。

solution

首先考虑这个东西和贪心的关系。

对于任意给定的定价 w_i \in \{1, 2\}，小 R 能买到的最大价值实际上等价于直接选取原价最大的 m 个糖果。因此，题目等价于：有多少种方案，使得贪心策略选取的糖果总价值等于该定价方案下的 0/1 背包最优解。

按性价比 \dfrac{a_i}{w_i} 降序购买。

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

发现贪心策略在只有 1 和 2 两种重量时，仅在一种情况下会得到非最优解：

• 贪心过程中，因为剩余钱数为 1，跳过了一个性价比很高但买不起的 2 元糖果 u。

• 随后，用这 1 元钱买了一个 1 元糖果 v（或者没买任何东西，即 v 不存在，a_v=0）。

• 如果此时，在已经购买的 1 元糖果集合中，存在一个糖果 z，满足 a_u > a_z + a_v（即把 z 和 v 换成 u 会更优），那么贪心策略就失败了。

直接计算合法方案很难，我们考虑容斥。

我们需要统计满足上述导致失败的方案数。为了不重不漏，我们枚举第一个导致失败的点 u 和用来填补的点 v。

将所有糖果按原价 a_i 从大到小排序。 枚举 u 作为第一个被跳过的 2 元糖果。根据 u，我们将其他糖果 i 分为三类：

• 集合 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 之后考虑。

对于固定的 u（w_u=2），要使其成为因没钱被跳过的糖果，必须满足在 u 之前被考虑并购买的糖果总花费恰好为 m-1，且包含 A 中的所有糖果（花费 w_i），以及 B 中 w_i=1 的糖果（花费 1）。

设 N_A = |A|，N_B = |B|，设 k_A 为 A 中取 w=2 的个数，k_B 为 B 中取 w=1 的个数。

总花费 = (N_A - k_A) \times 1 + k_A \times 2 + k_B \times 1 = N_A + k_A + k_B。