一些经典贪心策略的证明
zhenjianuo2025
·
·
算法·理论
1
题意：一张无向图 G，其中 i,j 间有连边当且仅当 a_i+a_j\ge s，其中 s 是定值。求 G 的最大匹配。
直接从大到小贪心是对的，但是可以证明更强的结论。
考虑任取一排列 p_1,\ldots,p_n，然后依次将 p_i 和 a_j\ge s-{a_{p_i}} 的 a_j 最小的 j（如果有）匹配。
反证，假设按照上述贪心策略得到的结果不是最优的。那么一定存在一个优于贪心策略的最优策略。那么考虑第一次按照贪心策略本应选择 u 和 v 匹配，而在最优策略中并没有选择将 u,v 匹配。两种情况：
- 没有匹配 u。将 u 和 v 匹配，并拆散 v 原有的匹配一定不劣。
-
我们就得到了一个不劣于最优策略的新策略。对新策略继续归纳，归纳到最后，就会得到贪心策略，因此贪心策略一定不劣于最优策略，与假设的存在比贪心策略更优的策略矛盾。
2
题意：还是一张无向图 G，i,j 间有连边当且仅当 l_i+l_j\le s\le r_i+r_j。求 G 的最大匹配。
按 l_i 从大到小排序贪心选择满足 l_j\le s-l_i 且 r_j\ge s-r_i 的最小 r_j 匹配。
和例 1 的证法是一样的。假设 u,w_1，v,w_2 各是一对匹配，证明一定可以调整成 u,v 和 w_1,w_2 各自匹配这样的形式。
## [3](https://atcoder.jp/contests/agc045/tasks/agc045_b)
（做法见题解区。）
证明：$f(L)$ 的贪心策略是最优的。
证明方法还是类似的。设在 $i$ 处的 ? 可以改成 ( 而在最终策略中是 )。考虑最小的 $i$。找到 $i$ 后面第一次操作的位置 $j$，将 $i$ 改为 (，$j$ 改为 )，仍然满足条件且最低点只会更高。
证明：$f(L+2)\le f(L)+2$。将 $L+2$ 方案的第一个 ( 改成 )，就得到了一个 $L$ 的方案。所以 $f(L)\ge f(L+2)-2$。
## [4]( https://codeforces.com/problemset/problem/2006/D)
证明将 $a$ 从小到大排序之后，排成 $c_1c_2...c_n=a_na_1a_{n-1}a_2\ldots$ 是最优的。
假设排列成 $b_1b_2...b_n$ 更优。这里有一种神奇的调整方法。首先比较 $b_1$ 和 $c_1$，若 $b_1\ne c_1$，由于 $c_1$ 是最大的，交换 $b_1$ 和 $c_1$ 在 $b$ 中出现的位置一定合法。再比较 $b_2$ 和 $c_2$，若 $b_2\ne c_2$，设 $b_p=c_2$。翻转 $c[2,p]$ 这段区间一定合法。因为已经保证了 $c_1$ 最大，$c_p$ 最小，所以 $c_2c_{p+1}\le c_1c_2\le k$，$c_1c_p\le c_1c_2\le k$。以此类推直到 $b=c$。
## [5]( https://www.luogu.com.cn/problem/P5290)
证明自底向上贪心，将儿子子树内的段按照最大内存排序后儿子子树间按照顺序依次匹配是最优的。
不同于之前的证明思路，证明对于每个 $c$，按照贪心策略得到的 $\ge c$ 的段的个数都是最小的。归纳假设子树内都已经是最优的，那么设儿子子树内 $\ge c$ 的段分别有 $d_1,d_2,...,d_m$ 个。则显然有下界 $\max\{d_1,...,d_m\}$，而按照贪心策略恰好取到下界，故得证。
## 6
题意：求带限制的 DAG 拓扑序。即 $l_u\le p_u\le r_u$，且对于 $(u,v)\in E$，$p_u<p_v$。
注意到 $l_u\le p_u$ 能推出 $l_u<p_v$，$p_v\le r_v\Rightarrow p_u<r_v$。将 $l_v$ 对 $l_u+1$ checkmax，$r_u$ 对 $r_v-1$ checkmin。然后跑 $l_u\le p_u\le r_u$ 的点与区间的贪心匹配。
证明这样是最优的。
充分性：
如果按照贪心策略得到的存在 $(u,v)\in E,p_u>p_v$。因为松弛过后的 $l_u<l_v,r_u<r_v$，根据贪心策略是不可能存在 $p_v$ 在 $p_u$ 之后被选这种情况的。（因为贪心顺序是按照 $r$ 从小到大。）
## [7]( https://atcoder.jp/contests/agc057/tasks/agc057_d)
比较综合的证明题。做法见题解区。
引理 1：$N=[(S-1)/2]$。首先，考虑 $x\in A$ 和 $S-1-x\in A$ 不能同时成立，所以 $N\le \frac{S-1}2$。当 $A=\{[\frac S2]+1,...,S-1\}$ 时，$N\ge [\frac{S-1}2]$，所以 $N=[\frac{S-1}2]$。
引理 2：当按照 **贪心策略** 确定了 $A'\subseteq \{1,...,[\frac{S-1}2]\}$，一定存在 $A'\subseteq A$。考虑 $x\notin A'$，将 $S-1-x$ 加入 $A'$。显然 $|A'|=N$。设 $a_1,a_2,...,a_k\in A'$ 且 $a_1+a_2+...+a_k=S$，$a_k>[\frac{S-1}2]$，则 $a_1+a_2+...+a_{k-1}=S-a_k$，按照贪心策略 $S-a_k$ 本应已经加入 $A'$，与 $a_k\in A'$ 矛盾。
#### 后面的题是一些 cf round 的简单题，主要在证明，可以留作习题。
大多数是作者口胡内容，因此证明细节上可能会有疏漏。
## [8](https://codeforces.com/problemset/problem/2152/H1)
显然我们只需要考虑所选的红色顶点是一个连通块的情况。因为如果不是，保留其中一个连通块一定不劣。
考虑树 $T$ 一个叶子 $u\in T$。考虑所有包含了 $u$ 的连通块 $S$，如果 $S$ 也包含了 $u$ 的父亲 $v$，$u,v$ 边权为 $w$，那么将 $x_u$ 尽可能多地转移到 $x_v$ 一定是不劣的。所以一定会使包含 $u$ 的最大连通块恰好取到 $k$，解得 $x_u=\max\{0,k-w\}$。重复剥叶子的过程。
## [9](https://codeforces.com/contest/2164/problem/C)
显然要先打 $c_i>0$ 的怪，最后打 $c_i=0$ 的怪。
考虑 $c_i>0$ 的怪，最优策略一定是按照 $b_i$ 从小到大逐个击败。因为如果不是，考虑交换相邻两个怪物 $b_i>b_{i+1}$。如果 $b_i$ 或 $b_{i+1}$ 中有一个怪没死，或打 $b_i$ 和 $b_{i+1}$ 使用的不是同一把剑，那么一定可以调整。如果打 $b_i$ 和 $b_{i+1}$ 使用的是同一把剑同样可以调整。
再考虑用哪一把剑去打 $b_i$。显然用攻击力 $\ge b_i$ 的攻击力最小的剑 $e$，得到 $\max(e,c_i),f$ 是最优的，因为如果选择了另一把更大的剑 $f$，$f\ge e$，得到 $e,\max(f,c_i)$，而 $\max(e,c_i)\ge e$ 且 $f\ge \max(f,c_i)$，$\max(e,c_i)\ge\max(f,c_i)$ 且 $f\ge e$ 至少有一个成立。所以选择 $e$ 比选择 $f$ 是一定更优的。
## [10](https://codeforces.com/contest/2035/problem/D)
考虑如何计算 $f(b_1,b_2,...,b_m)$。设 $b_i=b'_i2^{c_i}$，其中 $(2,b'_i)=1$。依次考虑 $b_m,b_{m-1},...,b_1$，选择 $b_i$ 后面最大的 $b_j$，将 $2^{c_i}$ 乘入 $b_j$。考虑使用调整法来证明策略的最优性：首先，$b_i$ 不会选择把自己的 $2^{c_i}$ 乘进多个数里，因为若 $x\le y$，$0<a\le b$，$x2^a+y2^b\le y2^{b+1}\le x+y2^{a+b}$。若 $x\le y,0<b<a$，$x2^a+y2^b\le y2^{a+1}\le x+y2^{a+b}$。
其次，如果 $b_i$ 把自己的 $2^{c_i}$ 乘进了 $b_k$，其中 $b_k<b_j$。根据上面的不等式，将所有在 $i$ 及 $i$ 之前乘进 $b_k$ 的数乘进 $b_j$ 里是不劣的。
## [11](https://codeforces.com/contest/2147/problem/E)
设最初的数组是 $a_i$，最终变成了 $b_i$。
考虑最终 $a_i$ 的 or 包含哪些 bit。设 $S$ 表示 $a_i$ 的 or，$T$ 表示 $b_i$ 的 or。考虑 $i\notin S,j\notin S$，如果 $i\in T,j\notin T$， $i\in b_k$，一定存在 $a_k\le t\le b_k,j\in t,i\notin t$，将 $b_i$ 调整为 $t$。显然代价不会变大，且 $b_i$ or 的 popcount 不会变小。因此考虑 $T$，一定形如 $T=S\cup \{0,1,...,k\}$ 或者 $T=S$。
枚举 $k$ 之后，考虑怎么求出最小的代价。考虑第 $i=k-1,...,0$ 位，如果说 $b_i$ 的 or 已经包含了第 $i$ 位，则无需再操作，否则选择后 $i$ 位最大的一个 $b_j$ 进位到 $2^i$，并将后 $i-1$ 位设成 0。
证明考虑使用归纳法。
假设只考虑 $i$ 之前的二进制位已经是最优的，推出 $i$ 也是最优的。
反证。设按照贪心策略选择的是 $b_j$，而按照最优策略选择的是 $b_k$。考虑调整，将 $b_j$ 第 $i$ 位变成 1，$b_k$ 第 $i$ 位变成 0，同时交换 $b_j$ 和 $b_k$ 的后 $i-1$ 位。显然仍然满足 $b_j\ge a_j,b_k\ge a_k$，且 $\sum_{x=1}^n b_x$ 不变。所以最优策略一定会选择 $b_j$，与假设矛盾。