题解：P11628 [WC2025] 猫粮

dyc2022 · 2025-02-03 10:49:10 · 题解

由于每袋猫粮最多只有 m-1 克，因此一只猫至少要吃 2 袋猫粮才能吃饱；而因为共有 2 \times n 袋猫粮，因此一只猫最多也只能吃 2 袋猫粮。

由于每只猫都要吃饱，因此一只猫至少吃 m 克猫粮；而因为猫粮总重量为 n \times m，因此一只猫最多也只能吃 m 克猫粮。

我们会发现，我们可以使用以下的方案来喂猫：

先扔出一袋优质猫粮，然后给吃到优质猫粮的小猫吃一袋普通猫粮，使其恰好吃饱。

那么如果满足重排 b 数组后能够对于每个 i 有 a_i + b_i = m，则一定有解。

这时自信提交，结果连大样例都过不了。

我们观察大样例可以发现，按照上述方法喂猫时，当还剩下 2 只猫时，我们会剩下 2 袋优质猫粮和 2 袋普通猫粮。我们这时候也可以把一只猫用两袋普通猫粮喂饱，然后把另一只猫用两个优质猫粮喂饱。这个时候，需要满足两袋普通猫粮的和为 m，两袋优质猫粮的和为 m。

这时自信提交，在 selfEval 上只获得了 65 分。

我们这时候发现了题目有『保证任意两袋猫粮的重量互不相同』这一档部分分，这十分有提示性。

我们想到，局限 不能有太多猫只吃优质猫粮 的问题，在于优质猫粮是等概率地落入当前所有猫中，因此我们无法将其“定向”。但是，如果我们最后剩下 k 只猫和 2 \times k 袋优质猫粮，如果这 2 \times k 袋优质猫粮质量均为 \frac{m}{2}，则不管这些猫粮以什么顺序被什么猫吃下，最后总能填饱这所有猫。这个充分性也显然。

所以讨论以上三种情况即可。

这时自信提交，在 selfEval 上获得了 100 分。