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

yyyx_ · 2025-11-29 17:22:43 · 题解

希望大家永远忘了我。

这个贪心策略是学习入门背包问题时就证伪的。

由于体积只有 1,2，那么贪心策略不优当且仅当：

1. 背包体积仅剩 2，一个体积为 2 的物品 x 和两个体积为 1 的物品 y,z 竞争体积，且 a_x>a_y+a_z,a_y>\frac{a_x}{2}>a_z；

2. 背包体积仅剩 2，一个体积为 2 的物品 x 和一个体积为 1 的物品 y 竞争体积，且 a_x > a_y,a_y>\frac{a_x}{2}。

先将 a 从大到小排序。

对于第一种情况，考虑 lim_i 表示 \forall j\in [1,lim_i],\frac{a_j}{2}\ge a_i。[1,lim_i] 中所有物品的性价比始终高于 i，即 [1,lim_i] 中所有物品都会在 i 之前被取走。那么我们就枚举 k 表示 [1,lim_i] 中体积等于 2 的物品数，容易算出 [lim_i+1,i-1] 中需要几个为 1。

用 i 前面的凑满 m-2 个后，我们将 a_i 设为上面的 a_y，那我们需要使得 a_x 是 a_y 后的第一个数（这样不会记重）。显然这个 x=m-1+k，因为前面的元素若除以 2 就会在 \frac{a_x}{2} 前面，而这和我们钦定的不一样。而 [x+1,i-1] 这一段就一定除以 2 了，原因类似。对于满足 a_j\le a_x-a_i 的 j 都可以和 i,x 构成第一种情况（大的满足后可以直接除以 2，这样就轮到次大的了），显然 k 从小到大枚举，\min j 单调不升。直接对着计算即可。

对于第二种情况，发现实质是第一种情况的特殊情况，一起做即可。

时间复杂度 \mathcal{O}(n^2)。