专栏文章

一些经典贪心策略的证明

zzhenjianuo2025
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mi4da0ce
此快照首次捕获于
2025/11/18 17:24
4 个月前
此快照最后确认于
2025/12/01 22:14
3 个月前
查看原文

1

题意：一张无向图 GG，其中 i,ji,j 间有连边当且仅当 ai+aj≥sa_i+a_j\ge s，其中 ss 是定值。求 GG 的最大匹配。
直接从大到小贪心是对的，但是可以证明更强的结论。
考虑任取一排列 p1,…,pnp_1,\ldots,p_n，然后依次将 pip_i 和 aj≥s−apia_j\ge s-{a_{p_i}} 的 aja_j 最小的 jj（如果有）匹配。
反证，假设按照上述贪心策略得到的结果不是最优的。那么一定存在一个优于贪心策略的最优策略。那么考虑第一次按照贪心策略本应选择 uu 和 vv 匹配，而在最优策略中并没有选择将 u,vu,v 匹配。两种情况：
  1. 没有匹配 uu。将 uu 和 vv 匹配，并拆散 vv 原有的匹配一定不劣。
  2. uu 的匹配为 w1w_1，aw1≥ava_{w_1}\ge a_v。如果 vv 没有匹配那么拆散 u,w1u,w_1 重新匹配 u,vu,v 是不劣的。否则设 vv 的匹配为 w2w_2。因为 aw2+av≥s,aw1≥ava_{w_2}+a_v\ge s,a_{w_1}\ge a_v 因此 aw2+aw1≥sa_{w_2}+a_{w_1}\ge s，将 u,vu,v 匹配，w1,w2w_1,w_2 匹配不劣。
我们就得到了一个不劣于最优策略的新策略。对新策略继续归纳，归纳到最后，就会得到贪心策略，因此贪心策略一定不劣于最优策略，与假设的存在比贪心策略更优的策略矛盾。

2

题意：还是一张无向图 GG，i,ji,j 间有连边当且仅当 li+lj≤s≤ri+rjl_i+l_j\le s\le r_i+r_j。求 GG 的最大匹配。
按 lil_i 从大到小排序贪心选择满足 lj≤s−lil_j\le s-l_i 且 rj≥s−rir_j\ge s-r_i 的最小 rjr_j 匹配。
和例 1 的证法是一样的。假设 u,w1u,w_1，v,w2v,w_2 各是一对匹配，证明一定可以调整成 u,vu,v 和 w1,w2w_1,w_2 各自匹配这样的形式。
lu+lw1≤sl_u+l_{w_1}\le s，lw2≤lul_{w_2}\le l_u，所以 lw1+lw2≤sl_{w_1}+l_{w_2}\le s。rv+rw2≥sr_v+r_{w_2}\ge s，又 rw1≥rvr_{w_1}\ge r_v 所以 rw1+rw2≥sr_{w_1}+r_{w_2}\ge s，得证。

3

（做法见题解区。）
证明：f(L)f(L) 的贪心策略是最优的。
证明方法还是类似的。设在 ii 处的 ? 可以改成 ( 而在最终策略中是 )。考虑最小的 ii。找到 ii 后面第一次操作的位置 jj，将 ii 改为 (，jj 改为 )，仍然满足条件且最低点只会更高。
证明：f(L+2)≤f(L)+2f(L+2)\le f(L)+2。将 L+2L+2 方案的第一个 ( 改成 )，就得到了一个 LL 的方案。所以 f(L)≥f(L+2)−2f(L)\ge f(L+2)-2。

4

证明将 aa 从小到大排序之后，排成 c1c2...cn=ana1an−1a2…c_1c_2...c_n=a_na_1a_{n-1}a_2\ldots 是最优的。
假设排列成 b1b2...bnb_1b_2...b_n 更优。这里有一种神奇的调整方法。首先比较 b1b_1 和 c1c_1，若 b1≠c1b_1\ne c_1，由于 c1c_1 是最大的，交换 b1b_1 和 c1c_1 在 bb 中出现的位置一定合法。再比较 b2b_2 和 c2c_2，若 b2≠c2b_2\ne c_2，设 bp=c2b_p=c_2。翻转 c[2,p]c[2,p] 这段区间一定合法。因为已经保证了 c1c_1 最大，cpc_p 最小，所以 c2cp+1≤c1c2≤kc_2c_{p+1}\le c_1c_2\le k，c1cp≤c1c2≤kc_1c_p\le c_1c_2\le k。以此类推直到 b=cb=c。

5

证明自底向上贪心，将儿子子树内的段按照最大内存排序后儿子子树间按照顺序依次匹配是最优的。
不同于之前的证明思路，证明对于每个 cc，按照贪心策略得到的 ≥c\ge c 的段的个数都是最小的。归纳假设子树内都已经是最优的，那么设儿子子树内 ≥c\ge c 的段分别有 d1,d2,...,dmd_1,d_2,...,d_m 个。则显然有下界 max⁡{d1,...,dm}\max\{d_1,...,d_m\}，而按照贪心策略恰好取到下界，故得证。

6

题意：求带限制的 DAG 拓扑序。即 lu≤pu≤rul_u\le p_u\le r_u，且对于 (u,v)∈E(u,v)\in E，pu<pvp_u<p_v。
注意到 lu≤pul_u\le p_u 能推出 lu<pvl_u<p_v，pv≤rv⇒pu<rvp_v\le r_v\Rightarrow p_u<r_v。将 lvl_v 对 lu+1l_u+1 checkmax，rur_u 对 rv−1r_v-1 checkmin。然后跑 lu≤pu≤rul_u\le p_u\le r_u 的点与区间的贪心匹配。
证明这样是最优的。
充分性： 如果按照贪心策略得到的存在 (u,v)∈E,pu>pv(u,v)\in E,p_u>p_v。因为松弛过后的 lu<lv,ru<rvl_u<l_v,r_u<r_v，根据贪心策略是不可能存在 pvp_v 在 pup_u 之后被选这种情况的。（因为贪心顺序是按照 rr 从小到大。）

7

比较综合的证明题。做法见题解区。
引理 1：N=[(S−1)/2]N=[(S-1)/2]。首先，考虑 x∈Ax\in A 和 S−1−x∈AS-1-x\in A 不能同时成立，所以 N≤S−12N\le \frac{S-1}2。当 A={[S2]+1,...,S−1}A=\{[\frac S2]+1,...,S-1\} 时，N≥[S−12]N\ge [\frac{S-1}2]，所以 N=[S−12]N=[\frac{S-1}2]。
引理 2：当按照 贪心策略 确定了 A′⊆{1,...,[S−12]}A'\subseteq \{1,...,[\frac{S-1}2]\}，一定存在 A′⊆AA'\subseteq A。考虑 x∉A′x\notin A'，将 S−1−xS-1-x 加入 A′A'。显然 ∣A′∣=N|A'|=N。设 a1,a2,...,ak∈A′a_1,a_2,...,a_k\in A' 且 a1+a2+...+ak=Sa_1+a_2+...+a_k=S，ak>[S−12]a_k>[\frac{S-1}2]，则 a1+a2+...+ak−1=S−aka_1+a_2+...+a_{k-1}=S-a_k，按照贪心策略 S−akS-a_k 本应已经加入 A′A'，与 ak∈A′a_k\in A' 矛盾。

后面的题是一些 cf round 的简单题，主要在证明，可以留作习题。

大多数是作者口胡内容，因此证明细节上可能会有疏漏。

8

显然我们只需要考虑所选的红色顶点是一个连通块的情况。因为如果不是，保留其中一个连通块一定不劣。
考虑树 TT 一个叶子 u∈Tu\in T。考虑所有包含了 uu 的连通块 SS，如果 SS 也包含了 uu 的父亲 vv，u,vu,v 边权为 ww，那么将 xux_u 尽可能多地转移到 xvx_v 一定是不劣的。所以一定会使包含 uu 的最大连通块恰好取到 kk，解得 xu=max⁡{0,k−w}x_u=\max\{0,k-w\}。重复剥叶子的过程。

9

显然要先打 ci>0c_i>0 的怪，最后打 ci=0c_i=0 的怪。
考虑 ci>0c_i>0 的怪，最优策略一定是按照 bib_i 从小到大逐个击败。因为如果不是，考虑交换相邻两个怪物 bi>bi+1b_i>b_{i+1}。如果 bib_i 或 bi+1b_{i+1} 中有一个怪没死，或打 bib_i 和 bi+1b_{i+1} 使用的不是同一把剑，那么一定可以调整。如果打 bib_i 和 bi+1b_{i+1} 使用的是同一把剑同样可以调整。
再考虑用哪一把剑去打 bib_i。显然用攻击力 ≥bi\ge b_i 的攻击力最小的剑 ee，得到 max⁡(e,ci),f\max(e,c_i),f 是最优的，因为如果选择了另一把更大的剑 ff，f≥ef\ge e，得到 e,max⁡(f,ci)e,\max(f,c_i)，而 max⁡(e,ci)≥e\max(e,c_i)\ge e 且 f≥max⁡(f,ci)f\ge \max(f,c_i)，max⁡(e,ci)≥max⁡(f,ci)\max(e,c_i)\ge\max(f,c_i) 且 f≥ef\ge e 至少有一个成立。所以选择 ee 比选择 ff 是一定更优的。

10

考虑如何计算 f(b1,b2,...,bm)f(b_1,b_2,...,b_m)。设 bi=bi′2cib_i=b'_i2^{c_i}，其中 (2,bi′)=1(2,b'_i)=1。依次考虑 bm,bm−1,...,b1b_m,b_{m-1},...,b_1，选择 bib_i 后面最大的 bjb_j，将 2ci2^{c_i} 乘入 bjb_j。考虑使用调整法来证明策略的最优性：首先，bib_i 不会选择把自己的 2ci2^{c_i} 乘进多个数里，因为若 x≤yx\le y，0<a≤b0<a\le b，x2a+y2b≤y2b+1≤x+y2a+bx2^a+y2^b\le y2^{b+1}\le x+y2^{a+b}。若 x≤y,0<b<ax\le y,0<b<a，x2a+y2b≤y2a+1≤x+y2a+bx2^a+y2^b\le y2^{a+1}\le x+y2^{a+b}。
其次，如果 bib_i 把自己的 2ci2^{c_i} 乘进了 bkb_k，其中 bk<bjb_k<b_j。根据上面的不等式，将所有在 ii 及 ii 之前乘进 bkb_k 的数乘进 bjb_j 里是不劣的。

11

设最初的数组是 aia_i，最终变成了 bib_i。
考虑最终 aia_i 的 or 包含哪些 bit。设 SS 表示 aia_i 的 or，TT 表示 bib_i 的 or。考虑 i∉S,j∉Si\notin S,j\notin S，如果 i∈T,j∉Ti\in T,j\notin T， i∈bki\in b_k，一定存在 ak≤t≤bk,j∈t,i∉ta_k\le t\le b_k,j\in t,i\notin t，将 bib_i 调整为 tt。显然代价不会变大，且 bib_i or 的 popcount 不会变小。因此考虑 TT，一定形如 T=S∪{0,1,...,k}T=S\cup \{0,1,...,k\} 或者 T=ST=S。
枚举 kk 之后，考虑怎么求出最小的代价。考虑第 i=k−1,...,0i=k-1,...,0 位，如果说 bib_i 的 or 已经包含了第 ii 位，则无需再操作，否则选择后 ii 位最大的一个 bjb_j 进位到 2i2^i，并将后 i−1i-1 位设成 0。
证明考虑使用归纳法。
假设只考虑 ii 之前的二进制位已经是最优的，推出 ii 也是最优的。
反证。设按照贪心策略选择的是 bjb_j，而按照最优策略选择的是 bkb_k。考虑调整，将 bjb_j 第 ii 位变成 1，bkb_k 第 ii 位变成 0，同时交换 bjb_j 和 bkb_k 的后 i−1i-1 位。显然仍然满足 bj≥aj,bk≥akb_j\ge a_j,b_k\ge a_k，且 ∑x=1nbx\sum_{x=1}^n b_x 不变。所以最优策略一定会选择 bjb_j，与假设矛盾。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...