先说一下官方证明在干嘛，再给你一版更短、更顺一点的完整证明。 --- ## 一、官方英文证明在说什么？ 核心结构就是两件事： 1. **把答案的上界分两种情形分析** 2. **证明这个贪心在两种情形里都能“刚好摸到上界”** ### 贪心算法本身 每次都选**当前社交值最大的两个人**聊天，各减一，并重复直到剩下的人中，社交值 gt;0$ 的人数不足 2。 这是我们要证明正确的策略。 --- ### 思想 1：如果有“绝对大佬”，那他一定撑满全场 设 $S = \sum a_i$，考虑是否存在某个 $i$，使得： $ a_i \ge S - a_i $ 也就是这个人，一个人大于等于其他所有人的总和——“绝对大佬”。 - **上界**： 这位大佬最多能和别人聊多少次？ 每次聊，必然要消耗他 1 点、别人 1 点。 但别人总共只有 $S - a_i$ 点可消耗，所以大佬最多参加 $S - a_i$ 次聊天。 每次聊天消耗 2 点社交值，所以总对话次数 $ k \le S - a_i. $ - **贪心一定每次都选他**： 每次聊完一次，大佬减 1，其他人总和也减 1，所以 $ a_i \ge S - a_i \Rightarrow a_i - 1 \ge (S - a_i) - 1 $ 始终保持“大佬的值 $\ge$ 其他人的总和”，所以他一直是**全场最大**，甚至比任何单个人都大。 因此，贪心每次都会选他作为参与者之一。 于是贪心会恰好安排他和所有人聊到别人社交耗尽为止，做到 $S - a_i$ 次聊天，刚好达到上界。 这就是**情况 1**：有绝对大佬时，答案是 $S - a_i$，贪心达到了。 --- ### 思想 2：否则就没有大佬，最多就是 $\lfloor S/2 \rfloor$ 如果没有任何 $i$ 满足 $a_i \ge S - a_i$，就说明 $ \forall i, a_i < S - a_i \quad\Rightarrow\quad a_i < \frac{S}{2}, $ 没有人占半数以上。 - **上界**： 因为每次聊天消耗总和 2，显然 $ k \le \left\lfloor \frac{S}{2} \right\rfloor. $ - **要证贪心能“把能聊的都聊完”**： 也就是说，贪心结束时，剩下总社交值 $S_{\text{end}}$ 要么是 0，要么是 1，这样 $ k = \frac{S - S_{\text{end}}}{2} = \left\lfloor \frac{S}{2} \right\rfloor. $ 官方证明的思路是： 看**最后一次对话之后的状态**，分几种情况： 1. **剩 0 个人**：总和是 0，做了 $S/2$ 次，完美。 2. **剩 1 个人社交值 = 1**：总和是 1，做了 $(S-1)/2$ 次，仍然是 $\lfloor S/2 \rfloor$。 3. **危险情况：剩 1 个人，社交值 gt; 1$**。 如果出现这种情况，他们就倒着分析，去看**最后一轮对话参与的是谁**，发现： - 因为我们每次都选当前最大的两个，所以最后一轮也必须包含这个人； - 这样往前倒推，可以一步步证明：在历史上任意一个时间点，这个剩下的家伙的社交值都大于其他所有人的总和； - 换句话说，这其实是**情况 1 的“有大佬”那种场景**。而我们这里谈的是情况 2，矛盾。 所以： - 如果一开始不是“有大佬”情况，而且过程里从来没有出现“有人比其他总和大”，那最终就不可能剩下一个人还大于 1。 - 因此最终总和只能是 0 或 1，聊天数就恰好是 $\lfloor S/2 \rfloor$。 这就是**情况 2**：无绝对大佬时，答案是 $\lfloor S/2 \rfloor$，贪心也达到了。 --- ## 二、基于官方思路的“简洁版证明” 下面给你一版精简但完整的证明（可以直接当题解里的“证明贪心正确性”的部分）。 --- 记初始社交值为 $a_1,\dots,a_n$，总和为 $ S = \sum_{i=1}^n a_i, $ 一次对话会选两个不同的人，各自社交值减 1。 我们的贪心：**每次选当前社交值最大的两个人对话**，重复直到无法再选。 ### 1. 两个通用上界 1. 每次对话消耗总社交值 2，因此对话次数 $k$ 必然满足 $ k \le \left\lfloor \frac{S}{2} \right\rfloor. \tag{1} $ 2. 如果存在某个最大值下标 $i$，令 $M=a_i$，其余人总和为 $R = S - M$，则第 $i$ 个人最多只能参加 $R$ 次对话（每次跟别人消耗 1 点，而别人总共只有 $R$ 点），所以 $ k \le R = S - M. \tag{2} $ 接下来证明：贪心算法总能达到上述上界中的最小值。 --- ### 2. 情况 1：存在“绝对大佬” 若存在 $i$ 使得 $ a_i \ge S - a_i, $ 记 $M = a_i$，$R = S - M$。由 (2) 知 $k \le R$。 注意每次对话若选中第 $i$ 个人和一个别人，则： - 第 $i$ 个人的社交值减为 $M-1$； - 其他人的总和也变成 $R-1$； 于是 $ (M-1) \ge (R-1) $ 依然成立，即在整个过程中第 $i$ 个人的社交值始终不小于其他人总和，从而大于等于任何单个人的社交值——他始终是**当前最大的人**。 因此贪心算法在每一轮都会选他和某个还没耗尽的人对话，直到其他人社交值全为 0 为止。这样对话次数恰为 $ k = R = S - M, $ 刚好达到上界 (2)，所以在这类实例中贪心是最优的。 --- ### 3. 情况 2：不存在“绝对大佬” 否则，对所有 $i$ 都有 $ a_i < S - a_i \Rightarrow a_i < \frac{S}{2}. $ 由 (1) 知 $k \le \lfloor S/2 \rfloor$。 我们证明贪心也恰好做到 $k = \lfloor S/2 \rfloor$。 设算法结束时剩余总社交值为 $S_{\mathrm{end}}$。由于每次操作总和减 2，有 $ k = \frac{S - S_{\mathrm{end}}}{2}. $ 显然如果 $S_{\mathrm{end}} \in \{0,1\}$，则 $k = \lfloor S/2 \rfloor$，结论成立。 因此只需证明：**在本情况中，不可能出现 $S_{\mathrm{end}} \ge 2$ 的终态**。 假设为反证：最终只剩下一个人 $p$，其社交值为 $L \ge 2$，其他人均为 0。 考虑最后一次对话： - 贪心总是选当前社交值最大的两个， - 而最后剩下来的这个人 $p$ 的剩余值 $L \ge 2$，因此在最后一轮之前，他的值已经至少是 2，而其他人至多是 1； - 所以最后一轮对话中，这个 $p$ 一定也是参与者之一（否则，两个“最大值”为 1 的人先聊完离场，$p$ 不可能剩下 $L \ge 2$）。 倒着看整个过程，可以逐步推出：在每一时刻，$p$ 的社交值都严格大于其他所有人的总和（因为每次回退一轮，对 $p$ 和“其他总和”都各加 1），这就意味着在某个时刻曾经满足 $ a_p \ge \sum_{j\neq p} a_j, $ 也就是我们其实处在**情况 1** 的场景，而不是情况 2，这与假设矛盾。 因此在“没有大佬”的初始条件下，终态不可能有唯一一人剩余 $L\ge 2$。 只能是： - 所有人耗尽：$S_{\mathrm{end}} = 0$，或 - 只剩一人社交值为 1：$S_{\mathrm{end}} = 1$。 两种情况对应的对话数都是 $ k = \frac{S - S_{\mathrm{end}}}{2} = \left\lfloor \frac{S}{2} \right\rfloor. $ 于是贪心在情况 2 中同样达到上界。 --- ### 4. 结论 综合两种情况： - 若存在 $i$ 使 $a_i \ge S - a_i$，最优答案是 $S - a_i$，贪心会每次选这个“绝对大佬”参与对话，做到恰好 $S - a_i$ 次； - 否则最优答案是 $\left\lfloor S/2 \right\rfloor$，贪心最终会把剩余总和压到 0 或 1，从而做到 $\left\lfloor S/2 \right\rfloor$ 次。 因此，“**每次选择当前社交值最大的两个人对话**”这一贪心策略总是得到最大可能的对话次数，证明完毕。 --- 如果你愿意，我也可以再帮你把这个简洁证明翻译成英文版本，方便你在 CF 上写 editorial-style 解答。