题解：P11399 [Code+#8 初赛] 集合划分

xxseven · 2024-12-18 19:19:12 · 题解

首先做一步转化：最大值小于另外两个值的和，等价于最大值小于总和的一半。

直接给出结论：按蛋糕重量从大到小考虑，分配给当前持有蛋糕重量最小的人，如果有解那么必定能构造出合法解。

证明：

以下记三个人的当前持有重量分别为 a_1,a_2,a_3 且 a_1 \le a_2 \le a_3 \lt \frac{sum}{2}，蛋糕总重为 sum，当前考虑的蛋糕重量为 x。

要想使得当前情况下无解，必须有 x+a_1 \ge \frac{sum}{2}。因为前面任何一块蛋糕都不比 x 轻，因此有 x \le a_1 \le a_2 \le a_3。

那么可以得到 x+a_1+a_2+a_3 \ge sum，当且仅当不等号左边四个数相等时取等，且取等时必有 n=4 且所有蛋糕重量相等，这种情况显然无解。

因此当有解时取等条件不成立，不可能有 x+a_1+a_2+a_3 \gt sum，所以 x+a_1 \ge \frac{sum}{2} 必然不成立，所以总能构造出合法的解。

提交记录。