下面给出一份**完整、统一排版**的证明，把你想要的「情况 1」+「情况 2」都合在一起，结构清晰、可以直接当题解里的正式证明使用。 --- # 题目抽象与贪心策略 有 $n$ 个人，第 $i$ 个人有 $a_i \ge 0$ 个任务。每次操作可以： - 选择两个不同的人 $x \ne y$，要求 $a_x > 0, a_y > 0$； - 然后令 $a_x \leftarrow a_x - 1,\ a_y \leftarrow a_y - 1$。 问最多能进行多少次操作，并给出一种达到这个最大次数的配对方案。 记初始时任务总数为 $ S = \sum_{i=1}^n a_i, $ 并将初始数组排序为 $ a_1 \le a_2 \le \dots \le a_n. $ **贪心策略**： 每次从当前所有人中选出**任务数最多的两个人**进行配对，即： - 用一个大根堆维护所有当前任务数 gt;0$ 的人； - 每次取出堆中两项 $(x, idx_x)$、$(y, idx_y)$，各自减 $1$ 后若仍 gt;0$ 就再丢回堆中； - 堆中元素个数不足 $2$ 时停止。 我们要证明：这个贪心策略能得到**最大可能的操作次数**。 --- # 一般上界 每次操作总任务数减少 $2$，所以不管用什么策略，总操作次数 $k$ 必然满足 $ k \le \left\lfloor \frac{S}{2} \right\rfloor. \tag{1} $ 另外，记 $ M = \max_i a_i = a_n,\quad R = S - M = \sum_{i=1}^{n-1} a_i. $ 注意到对于任何策略： - 每次操作最多只能把「最大那个人」的任务减 $1$； - 但要想减少 TA 的任务，必须和某个「其他人」配对一次； - 而「其他人」一共只有 $R$ 个任务，所以最大那个人最多参加 $R$ 次操作。 因此还得到一个上界 $ k \le R = S - M. \tag{2} $ 综合两者可知：对任何策略都有 $ k \le \min\left( \left\lfloor \frac{S}{2} \right\rfloor,\ S - M \right). $ 接下来我们证明：**贪心策略在所有情形下都恰好达到这个上界**。 --- # 情况 1：$M > \left\lfloor \dfrac{S}{2} \right\rfloor$（存在“多数派”） 这等价于 $M > S - M$，即 $ a_n > \sum_{i=1}^{n-1} a_i. $ 此时「上界」由式 (2) 决定，即 $ k \le S - M = R. $ 我们证明：**贪心策略恰好能做 $R$ 次操作**，因此是最优的。 --- ## 1.1 第 $n$ 个人始终是唯一最大值 记 - 第 $n$ 个人为「重人」； - 在第 $t$ 次操作之前，他的任务数为 $M_t$； - 其他所有人的任务和为 $R_t$。 初始时 $ M_0 = M = a_n,\quad R_0 = R = S - a_n, $ 且由于 $M > R$，有 $ M_0 > R_0. $ 我们证明如下不变量： > **不变量 $\mathbf{P(t)}$：** > 在第 $t$ 次操作之前，有 $M_t > R_t$。 ### 基例（$t = 0$） 由 $M_0 = a_n > S - a_n = R_0$，命题 $\mathbf{P(0)}$ 成立。 ### 归纳步 假设在第 $t$ 次操作之前 $\mathbf{P(t)}$ 成立，即 $M_t > R_t$。 1. 由于 $R_t = \sum_{i \ne n} a_i$，对任一其他人 $i$ 有 $ a_i \le R_t < M_t, $ 因此**第 $n$ 个人的任务数严格大于每个其他人**，他是当前状态下的**唯一最大值**。 2. 贪心策略每一步都要从当前任务数最多的人中选两个不同的人，因此这一轮操作必然选中第 $n$ 个人和某个其他人配对。 3. 本轮操作后： - 第 $n$ 个人任务数减 $1$：$M_{t+1} = M_t - 1$； - 其他人的总和也减 $1$：$R_{t+1} = R_t - 1$。 于是 $ M_{t+1} - R_{t+1} = (M_t - 1) - (R_t - 1) = M_t - R_t > 0, $ 即 $M_{t+1} > R_{t+1}$，所以 $\mathbf{P(t+1)}$ 成立。 由数学归纳法，$\mathbf{P(t)}$ 对所有 $t$ 都成立。 因此：**只要还存在其他人有任务，第 $n$ 个人始终是唯一最大值，并且每次操作都必然参与配对。** --- ## 1.2 操作次数恰为 $R = S - M$ 每次操作都会让 - 「重人」的任务数 $M_t$ 减少 $1$； - 其他人的总任务数 $R_t$ 也减少 $1$。 初始时 $R_0 = R$。当进行了恰好 $R$ 次操作后，得到 $ R_R = R_0 - R = 0. $ 此时其他人任务全为 $0$，而 $\mathbf{P(R)}$ 仍然成立，说明「重人」此时仍有 $M_R > R_R = 0$ 个任务，但已无法再与任何人配对，算法终止。 因此贪心策略在这种情形下的操作次数为 $ k = R = S - M, $ 刚好达到上界 (2)，从而在 $M > \left\lfloor \dfrac{S}{2} \right\rfloor$ 的情形下，贪心是最优的。 --- # 情况 2：$M \le \left\lfloor \dfrac{S}{2} \right\rfloor$（不存在“多数派”） 这一情形下，由一般上界 (1) 可知任意策略最多只能做 $ k \le \left\lfloor \frac{S}{2} \right\rfloor $ 次操作。我们将证明：**贪心策略可以恰好做到这个次数**。 为此，我们分析贪心执行过程中的状态变化。 --- ## 2.1 状态与不变量 在第 $t$ 次操作之前，记： - 当前各人的任务数为某组非负整数（顺序可变）； - 总和为 $S_t$； - 最大值为 $M_t$。 初始时 $S_0 = S$，$M_0 = M$，并且在「情况 2」的前提下有 $ M_0 \le \left\lfloor \frac{S_0}{2} \right\rfloor. $ 我们要证明下面这个不变量： > **不变量 $\mathbf{Q(t)}$：** > 若此时还可以继续操作（即 $S_t \ge 2$ 且存在至少两个人任务数 gt;0$），则 > $ > M_t \le \left\lfloor \frac{S_t}{2} \right\rfloor > \quad\text{（即 }2M_t \le S_t\text{）}. > $ 一旦 $\mathbf{Q(t)}$ 一直成立到算法结束，我们就能推出： 最终总任务数 $S_{\mathrm{end}} \in \{0,1\}$，从而总操作次数为 $ k = \frac{S - S_{\mathrm{end}}}{2} = \left\lfloor \frac{S}{2} \right\rfloor. $ --- ## 2.2 基例 $t = 0$ 时，正是「情况 2」的前提条件： $ M_0 \le \left\lfloor \frac{S_0}{2} \right\rfloor, $ 所以 $\mathbf{Q(0)}$ 成立。 --- ## 2.3 归纳步：从第 $t$ 步到第 $t+1$ 步 假设在第 $t$ 次操作之前，$\mathbf{Q(t)}$ 成立，并且算法尚未结束，即 $S_t \ge 2$ 且存在至少两个任务 gt;0$ 的人。 把当前所有人的任务数排序为 $ b_1 \le b_2 \le \dots \le b_{n-1} \le b_n = M_t. $ 贪心策略会选出**当前最大的两个数** $b_{n}$ 与 $b_{n-1}$，各减 $1$。 操作后： - 新的总和为 $ S_{t+1} = S_t - 2; $ - 新的最大值记为 $M_{t+1}$（从修改后的数组中取最大即可）。 我们分几种情况讨论 $M_{t+1}$，并验证在需要时 $2M_{t+1} \le S_{t+1}$ 仍然成立。 --- ### 情形 A：最大值唯一（$b_n > b_{n-1}$） 此时只有 $b_n$ 一个数等于 $M_t$。操作后： - $b_n$ 变成 $b_n - 1$； - 其余各数都 $\le b_{n-1} < b_n$，因此都 $\le b_n - 1$； 所以新的最大值为 $ M_{t+1} = b_n - 1 = M_t - 1. $ 由归纳假设 $\mathbf{Q(t)}$，有 $2M_t \le S_t$，于是 $ 2M_{t+1} = 2(M_t - 1) = 2M_t - 2 \le S_t - 2 = S_{t+1}. $ 若 $S_{t+1} \ge 2$（即仍能继续操作），则 $ M_{t+1} \le \left\lfloor \frac{S_{t+1}}{2} \right\rfloor, $ 因此 $\mathbf{Q(t+1)}$ 成立。 --- ### 情形 B：最大值不唯一（$b_{n-1} = b_n = M_t$） 这时至少有两个数等于 $M_t$。同样进行一次操作后： - $b_{n-1}$ 和 $b_n$ 都从 $M_t$ 变为 $M_t - 1$； - 其余各数都 $\le M_t$，因此都 $\le \max{M_t, M_t-1}$。 我们再按「有多少个最大值」分两种子情况： #### B1. 恰好两个最大值 如果原来只有 $b_{n-1}$ 和 $b_n$ 等于 $M_t$，那么操作后所有数都 $\le M_t-1$ 且有至少一个等于 $M_t-1$，于是 $ M_{t+1} = M_t - 1. $ 推导与情形 A 完全相同，得到 $ 2M_{t+1} \le S_{t+1}, $ 若 $S_{t+1} \ge 2$，则 $\mathbf{Q(t+1)}$ 成立。 #### B2. 至少三个最大值 此时有 $b_{n-2} = b_{n-1} = b_n = M_t$（甚至可能更多个）。 操作后，$b_{n-1}, b_n$ 从 $M_t$ 变成 $M_t - 1$，但至少还有一个 $b_{n-2}$ 保持为 $M_t$，因此 $ M_{t+1} = M_t. $ 另一方面，由于至少有三个数等于 $M_t$，总和 $S_t$ 至少满足 $ S_t \ge 3M_t. $ - 若 $M_t = 1$： 此时 $S_t \ge 3$。操作后 $S_{t+1} = S_t - 2 \ge 1$。 - 如果 $S_{t+1} = 1$，说明已经只剩一个任务，算法自然终止，不再需要维护不变量； - 如果 $S_{t+1} \ge 2$，则 $ 2M_{t+1} = 2 \le S_{t+1}, $ 不变量 $\mathbf{Q(t+1)}$ 仍然成立。 - 若 $M_t \ge 2$： 由 $S_t \ge 3M_t$ 得 $ S_t - 2 \ge 3M_t - 2 \ge 2M_t, $ 因为 $3M_t - 2 - 2M_t = M_t - 2 \ge 0$。于是 $ 2M_{t+1} = 2M_t \le S_t - 2 = S_{t+1}. $ 若 $S_{t+1} \ge 2$，则 $\mathbf{Q(t+1)}$ 成立。 综上，在情形 B2 中，要么下一步已经无法继续（$S_{t+1} = 1$，算法终止），要么仍满足 $S_{t+1} \ge 2$ 且 $2M_{t+1} \le S_{t+1}$，即 $\mathbf{Q(t+1)}$ 成立。 --- ### 小结归纳步 无论是情形 A、B1 还是 B2，只要操作后还能继续（$S_{t+1} \ge 2$ 且存在两个任务 gt;0$ 的人），我们都证明了 $ M_{t+1} \le \left\lfloor \frac{S_{t+1}}{2} \right\rfloor. $ 因此 $\mathbf{Q(t)} \Rightarrow \mathbf{Q(t+1)}$ 成立。 结合基例，得到：对所有执行中的时刻 $t$，只要算法尚未结束，就有 $\mathbf{Q(t)}$ 成立。 --- ## 2.4 算法终止时的状态与操作次数 当贪心算法结束时，说明**不能再选出两个任务数 gt;0$ 的不同的人**。因此剩余任务的情况必然是： - 要么所有人任务都为 $0$，记为 $S_{\mathrm{end}} = 0$； - 要么恰好有一个人任务数为 $L \ge 1$，其余为 $0$，这时 $S_{\mathrm{end}} = L$。 我们证明此时 $L$ 不可能大于 $1$。 若存在唯一一个人任务数为 $L \ge 2$，则： - 最大值 $M_{\mathrm{end}} = L$； - 总和 $S_{\mathrm{end}} = L$； 必然有 $ M_{\mathrm{end}} = L > \frac{L}{2} = \frac{S_{\mathrm{end}}}{2}, $ 与不变量 $\mathbf{Q}$ 矛盾（因为在算法尚未继续之前，若 $S_{\mathrm{end}} \ge 2$，应该有 $M_{\mathrm{end}} \le \lfloor S_{\mathrm{end}}/2 \rfloor$）。 因此唯一的可能是： - $S_{\mathrm{end}} = 0$（所有任务被完全配对掉），或 - $S_{\mathrm{end}} = 1$（只剩下一个任务）。 综上， $ S_{\mathrm{end}} \in \{0, 1\}. $ 记总操作次数为 $k$，每次操作总任务数减少 $2$，于是 $ S_{\mathrm{end}} = S - 2k. $ 于是 $ S - 2k \in \{0, 1\} \quad\Longrightarrow\quad k = \frac{S - S_{\mathrm{end}}}{2} = \left\lfloor \frac{S}{2} \right\rfloor. $ 结合上界 (1) 可知：**在 $M \le \left\lfloor S/2 \right\rfloor$ 的情形下，贪心算法达到了任意策略的最大可能操作次数**。 --- # 总结：贪心策略的最优性 综合两种情形： 1. 若 $M > \left\lfloor \dfrac{S}{2} \right\rfloor$，则上界为 $k \le S - M$， 贪心策略在每一步都配对「重人 + 其他人」，恰好做了 $S - M$ 次操作，达到上界。 2. 若 $M \le \left\lfloor \dfrac{S}{2} \right\rfloor$，则上界为 $k \le \left\lfloor \dfrac{S}{2} \right\rfloor$， 利用不变量 $M_t \le \left\lfloor S_t/2 \right\rfloor$ 可以证明最终 $S_{\mathrm{end}} \in {0,1}$，从而 $k = \left\lfloor S/2 \right\rfloor$，同样达到上界。 因此，对任意初始任务数配置，**每次选当前任务数最多的两个人进行配对**的贪心策略，所取得的操作次数总是最大可能值。这就证明了 CF 1579D 中使用的贪心策略是正确且最优的。