贪心算法以及一些证明策略

以下 8 个问题都给出了相应贪心策略，但是为什么这些策略是正确的呢？请自己证明（提示：反证法）

---

4.1 装载问题

(1) 简单的装载问题

问题描述 有 n 件物品和一个容量为 C 的背包。第 i 件物品的重量是 w[i]。求解将哪些物品装入背包可物品数量最多。

贪心策略 将物品重量从小到大进行排序，优先挑重量轻的装入背包。

---

(2) 部分背包问题

问题描述 有 n 件物品和一个容量为 C 的背包。第 i 件物品的重量是 w[i]，价值是 v[i]。每个物体可以取走一部分，价值和重量按比例计算。求解将哪些物品装入背包可使价值总和最大。

贪心策略 将背包按照单价（价值/重量的比值）排序。从物美价廉（单价尽可能大）的物体开始挑起，直到背包装满或没有物体可拿。

---

(3) 乘船问题

问题描述 有 n 个人，第 i 个人的重量是 wi。每艘船的最大载重量都是 C，且最多能乘两个人。用最少的船装尽可能多的人。

贪心策略 让最轻的人和能与他同船的最重的人乘一条船。如果办不到，就一人一条船。

---

4.2 区间问题

(1) 选择不相交区间

问题描述 数轴上有 n 个开区间 (ai, bi)。选择尽量多的区间，使这些区间两两没有公共点。

贪心策略 按 bi 从小到大的顺序排序，然后一定选择第一个区间。接下来把所有与第一个区间相交的区间排除在外。这样在排序后再扫描一遍即可。

---

(2) 区间选点问题

问题描述 数轴上有 n 个闭区间 [ai, bi]。取尽量少的点，使得每个区间内都至少有一个点（不同区间内含有的点可以是同一个）。

贪心策略 把所有区间按 bi 从小到大排序（bi 相同时，a 从大到小排序），然后一定取第一个区间的最后一个点。

---

(3) 区间覆盖问题

问题描述 数轴上有 n 个闭区间 [ai, bi]。选择尽量少的区间来覆盖指定线段 [s, t]。

贪心策略

1. 预处理：扔掉不能覆盖 [s, t] 的区间。
2. 把各区间按 a 从小到大排序。如果区间 1 的起点不是 s，无解，否则选择起点在 s 的最长区间。
3. 选择此区间 [ai, bi] 后，问题转化为覆盖 [bi, t]，于是返回①，直到 [s, t] 被完全覆盖为止。

---

4.3 删数问题

问题描述 给出一个 N 位的十进制高精度数，要求从中删掉 S 个数字（其余数字相对位置不得改变），使剩余数字组成的数最小。

贪心策略

1. 每次找出最靠前的这样的一对数字 —— 两个数字紧邻，且前面的数字大于后面的数字，删除这对数字中靠前的一个。
2. 重复步骤 1，直至删去了 S 个数字或找不到这样的一对数。
3. 若还未删够 S 个数字，则舍弃末尾的部分数字，取前 N − S 个。

---

4.4 工序问题

问题描述 n 件物品，每件需依次在 A、B 机床上加工。已知第 i 件在 A、B 所需加工时间分别为 Ai、Bi，设计一加工顺序，使所需加工总时间最短。

贪心策略

1. 设置集合 F、M、S：先加工 F 中的，再加工 M 中的，最后加工 S 中的。
2. 对第 i 件，若 Ai > Bi，则归入 S；若 Ai = Bi，则归入 M；否则归入 F（“拉开时间差”）。
3. 对 F 中的元素按 Ai 从小到大排列，S 中的按 Bi 从大到小排列。

---

4.5 种树问题

问题描述 一条街道分为 n 个区域（按 1～n 编号），每个都可种一棵树。有 m 户居民，每户会要求在区域 i～j 区间内种至少一棵树。现求一个能满足所有要求且种树最少的方案。

贪心策略

1. 对于要求，以区间右端（升序）为首要关键字，左端（升序）为次要关键字排序。
2. 按排好的序依次考察这些要求，若未满足，则在其最右端的区域种树，这时可能会满足多个要求。

---

---

4.6 三值的排序

问题描述 排序是一种很频繁的计算任务。现在考虑最多只有三值的排序问题。一个实际的例子是，当我们给某项竞赛的优胜者按金银铜牌序的时候。

在这个任务中可能的值只有三种：1，2 和 3。我们用交换的方法把它排成升序的。 写一个程序计算出把给定的一个由 1、2、3 组成的数字序列排成升序所需的最少交换次数。

分析 为了使交换次数最小，我们想到了以下贪心策略：

1. 能不交换就不交换；
2. 如果能只用一次交换就完成归位，就不用两次交换。

由于排序之后是 111…222…333… 的形式，我们不妨按照排序之后的结果对原数据分区。 令 w(i,j) 表示数字 i 在 j 区的数量。例如 12231213 中 w(2,1)＝2。

• 按照①，在一区的 1、二区的 2、三区的 3 就不应该再被交换了。
• 按照②，在一区的 2 应该和二区的 1 进行交换，1 和 3、2 和 3 类似。

设这一次交换的步数为 A，则

$$A = \min\{w(1,2)+w(2,1)\} + \min\{w(1,3)+w(3,1)\} + \min\{w(2,3)+w(3,2)\} $$

接下来已经不能一步恢复两个数字了，就像 312 一样。这时只有先让一个数字归位，然后再交换另外两个。 这样，每三个数字需要用两步完成。

设这一次交换的步数为 B，则

$$B = \frac{S - 2A}{3} \times 2$$

其中 S 表示需交换的数字的总个数，即

$$S = w(1,2)+w(2,1)+w(2,3)+w(3,2)+w(1,3)+w(3,1)$$

最后将 A 和 B 相加，即最终结果。

---

4.7 田忌赛马

问题描述 大家都知道“田忌赛马”的故事。现在，田忌再一次和齐王赛马。他们各派出 N 匹马（N ≤ 2000）。 每场比赛，输的一方将要给赢的一方 200 两黄金，如果是平局的话，双方都不必拿出钱。

每匹马的速度值是固定而且已知的，而齐王出马也不管田忌的出马顺序。请问田忌该如何安排自己的马去对抗齐王的马，才能赢最多的钱？

---

分析 题目本身已经告诉我们怎样用二分图最佳匹配来解决这个问题： 把田忌的马放左边，把齐王的马放右边。

• 如果田忌的马 A 胜齐王的马 B，则连一条权为 200 的边；
• 如果平局，则连一条权为 0 的边；
• 如果输，则连一条权为 −200 的边。

但是复杂度太高，无法承受 N = 2000 的规模。

所以我们用贪心思想来分析：

1. 如果田忌剩下的马中最强的马都赢不了齐王剩下的最强的马，那么就用最差的一匹马去输给齐王最强的马。
2. 如果田忌剩下的马中最强的马可以赢齐王剩下的最强的马，那就用这匹马去赢。
3. 如果田忌剩下的马中最强的马和齐王剩下的最强的马打平，可以选择打平或者用最差的马输掉。

问题在于：第三条贪心策略存在分支，如果一概选择打平或一概选择输，都可能出错。

不过通过分析可知，田忌的出马方式一定是： 将自己的马排序，然后从两头取马和齐王的马进行比赛。

---

动态规划模型 设 f(i,j) 表示田忌从“头”取了 i 匹较强的马，从“尾”取了 j 匹较弱的马进行比赛所能得到的最大盈利。

状态转移方程为：

$$f(i,j) = \max\{ f(i, j-1) + g[n-(j-1)],\ f(i-1, j) + g(i) \} $$

其中 g(x) 表示田忌的第 x 匹马和齐王的第 i+j 匹马比赛时的收益：

• 胜为 200；
• 平为 0；
• 输为 −200。

---

4.8 小结

贪心算法指从问题的初始状态出发，通过若干次的贪心选择而得出最优值（或较优解）的一种解题方法。

贪心思想的本质是：每次都形成局部最优解，换一种说法，就是每次都处理出一个当前最好的方案。

除了本单元的问题，还有一些常见问题也是用贪心算法求解的：

• 建立哈夫曼树
• Prim 算法
• Kruskal 算法
• 拓扑排序

如果存在贪心性质，那么一定要采用贪心算法。因为它容易编写，容易调试，速度极快，并且节约空间。几乎可以说，它是所有算法中最好的。

然而，贪心算法并不总是正确的，因为并不是每次局部最优解都会与整体最优解之间有联系，往往靠贪心生成的解不是最优解。一般情况下，构造出贪心策略后要进行证明。

贪心还是一种思想。运用贪心思想，主要是为了分析出问题的一些本质，或者分析出低效算法中的冗余。合理地运用贪心思想，可以帮助运用其他算法解决问题。

---

0x00 一些进阶贪心

0x01 用两个元素的交换来推出贪心方法（邻项交换法）

这个方法适用于解决顺序问题或者安排问题，通过先解决小问题来总结出规律，从而解决出这个题目。

例题：P1080 [NOIP 2012 提高组] 国王游戏

这个题目就是典型的邻项交换法推贪心。

1.假设

我们先假设国王后面只有两个大臣，而且假设国王拿着的是 $a_0,b_0$，第一个大臣拿的是 $a_1,b_1$，第二个大臣拿的是 $a_2,b_2$，我们有两种顺序。

• 第一个大臣在前面，那么第一个大臣得到的奖金就是 $\frac{a_0}{b_1}$，第二个大臣拿到的奖金就是 $\frac{a_0\times a_1}{b_2}$，最高的奖赏就是 $\max{(\frac{a_0}{b_1},\frac{a_0\times a_1}{b_2})}$。

• 第二个大臣在前面，那么第二个大臣得到的奖金就是 $\frac{a_0}{b_2}$，第一个大臣拿到的奖金就是 $\frac{a_0\times a_2}{b_1}$，最高的奖赏就是 $\max{(\frac{a_0}{b_2},\frac{a_0\times a_2}{b_1})}$。

2.推导

现在我们就要来比较最高的奖赏，即比较 $\max{(\frac{a_0}{b_2},\frac{a_0\times a_2}{b_1})}$ 和 $\max{(\frac{a_0}{b_1},\frac{a_0\times a_1}{b_2})}$ 谁更小。

我们发现 $\frac{a_0}{b_1}$ 一定小于等于 $\frac{a_0\times a_2}{b_1}$（因为 $a_2$ 是大于 0 的整数，即 $a_2 \ge 1$，不会变小），同理 $\frac{a_0}{b_2}$ 一定小于等于 $\frac{a_0\times a_1}{b_2}$。所以我们可以将式 $[a]$ 转化为求

$$\min{(\frac{a_0\times a_1}{b_2},\frac{a_0\times a_2}{b_1})[a]} $$

的答案。

我们把 $\frac{a_0\times a_1}{b_2}$ 和 $\frac{a_0\times a_2}{b_1}$ 同时除 $a_0$，在乘上 $b_1\times b_2$，就把这两个式子化简为 $b_1\times a_1$ 和 $b_2\times a_2$。发现什么没有？我们把结果的大小比较转化为了大臣手上数的乘积比较，如果 $a_1\times b_1$ 小于 $a_2\times b_2$，那么就把 1 号大臣排在前面，否则排在后面。

例题：P1248 加工生产调度

1.假设

我们假设有两个产品 $x$ 和 $y$，$x$ 产品在 A 车间加工时间是 $a_x$，同理，其他的分别为 $b_x$、$a_y$、$b_y$。

• $x$ 产品先做，那么 $x$ 产品所有的时间就是 $a_x+b_x$，由于 $y$ 产品要等到 $x$ 产品加工完才行，那么 $y$ 产品在 A 车间加工就需要 $a_x+a_y$ 的时间（$a_x$ 的等待时间），而此时 $x$ 产品在 B 车间加工了 $a_y$ 的时间，还需要 $\max{(b_x-a_y,0)}$ 的时间加工，所以 $y$ 产品在 B 车间需要 $\max{(b_x-a_y,0)}+b_y$ 的时间加工。由于 $y$ 产品肯定是等到 $x$ 产品加工后才结束，所以花费的总时间是 $a_x+a_y+\max{(b_x-a_y,0)}+b_y$ 的时间。

• 同理 $y$ 产品先做就需要花费 $a_x+a_y+\max{(b_y-a_x,0)}+b_x$ 的时间。

2.推导

现在我们需要比较 $x$ 产品先做和 $y$ 产品先做的时间，即求出

$$\min(a_x+a_y+\max(b_x-a_y,0)+b_y,a_x+a_y+\max(b_y-a_x,0)+b_x)[b] $$

不难发现 $x\pm \max(a,b)=\max(x\pm a,x\pm b)$，对于 $\min$ 也成立，所以 $[b]$ 式就可以化简为：

$$\begin{array}{l} \min(a_x+a_y+\max(b_x,a_y)-a_y+b_y,a_x+a_y+\max(b_y,a_x)-a_x+b_x)\\ =\min(a_x+b_y+\max(b_x,a_y),a_y+b_x+\max(b_y,a_x))\\ =\min(\max(b_x,a_y)-a_y-b_x,\max(b_y,a_x)-a_x-b_y)+a_x+a_y+b_x+b_y\\ =\min(\max(-a_y,-b_x),\max(-a_x,-b_y))+a_x+a_y+b_x+b_y\\ \end{array}$$

至于继续的推导，需要用到 Johnson 定理，感兴趣的读者可以自己去了解一下。

最终的排序方法是将 $\min(a_x,a_y) < \min(b_x,b_y)$ 的 $x$ 排前面。

例题：P1842 奶牛玩杂技

1.假设

假设有两头牛 $a$ 和 $b$，那么它们的体重分别是 $w_a$ 和 $w_b$，力量是 $s_a$ 和 $s_b$。

如果现在只有这两头牛，那么：

• $a$ 在上面，那么 $a$ 的压扁指数为 $-s_a$，$b$ 的压扁指数为 $w_a-s_b$，总压扁指数为 $\max(-s_a,w_a-s_b)$。（注意这里不能直接省去 $-s_a$，虽然它为负数，但当 $w_a-s_b<-s_a$ 时就会取 $-s_a$。）

• $b$ 在上面，那么同理，总压扁指数为 $\max(-s_b,w_b-s_a$)。

2.进一步的假设

如果我们要使 $a$ 在上面，那么我们该怎么做呢？

我们需要满足 $\max(-s_a,w_a-s_b) < \max(-s_b,w_b-s_a)$。

易证 $-s_a < w_b-s_a,-s_b < w_a-s_b$ 所以 $\max(-s_a,w_a-s_b)$ 就可以变为 $w_a-s_b$，同理 $\max(-s_b,w_b-s_a)$ 变为 $w_b-s_a$。

因为我们要使 $w_a-s_b < w_b-s_a$，简单移项便可以得到 $w_a+s_a<w_b+s_b$。

所以如果要使 $a$ 在上面，必须要 $w_a+s_a<w_b+s_b$。

0x02 区间类贪心（区间类问题）

这个方法适用于一系列的区间取舍问题，最基础的问题有：

1. 区间选点（在 $n$ 个区间放尽量少的点，使得每个区间都有点）
2. 区间覆盖（选择尽量少的区间覆盖整个线段）
3. 区间分组（将区间分成尽量少的组使得组内的区间两两互不相交）

区间类问题的常用方法是按右端点排序，方便解决区间取舍后对下一个区间的影响（如果不按右端点排序就有后效性了，不能用贪心解决）。

例题：P2255 [USACO14JAN] Recording the Moolympics S

同样，我们先按右端点排序，然后因为有两个节目可以同时录制，我们用 $p_1$ 和 $p_2$ 来代表两个节目的结束时间。

贪心策略：由于靠前的节目是结束时间更小的，所以结束后可以更快安排下一个节目，所以我们只需要按右端点排序后挨个判断节目是否可以即可。

0x03 数据结构优化贪心——并查集

在有些时候，贪心的复杂度为 $n^2$，其中一个 $n$ 的复杂度是寻找前面满足条件的元素所需的复杂度，所以我们可以用并查集优化。

例题：U213773 家庭作业

我们很容易推出贪心策略：先选得分大的，如果这个作业有时间就做，没时间直接舍去，但由于每次查找之前的时间都需要 $n$，总复杂度为 $n^2$，考虑并查集优化。

我们定义 $f_i$ 为 $i$ 天前的第一个空闲时间，那么查找这个作业是否可以就是 $find(x)$，复杂度为 $1$（路径压缩）。

例题：P1525 [NOIP 2010 提高组] 关押罪犯

很明显，我们需要让危害性较大的两个罪犯分到两个监狱里。我们用 $f_i$ 表示第 $i$ 个人和 $f_i$ 个人放在一个监狱里，$b_i$ 表示跟 $i$ 仇恨度最大的人是谁。

很明显，如果现在 $b_x$ 已经有值了，所以为了他们并不互相冲突，只能将 $b_x$ 和 $y$ 放在一个监狱里面，如果没有 $b_x$，根据贪心策略，肯定将 $x$ 和 $y$ 放在两个监狱里。

0x04 数据结构优化贪心——优先队列

贪心中查找最大或最小值且两个元素在同一位置的查找范围一样，那么就可以用 $\log n$ 的复杂度取代 $n$ 的暴力枚举。

例题：[ABC407E] Most Valuable Parentheses

很明显，我们只要满足左括号的数量等于右括号的数量且在任何一个 $1\sim i$ 的序列中的左括号都要大于右括号，所以我们只需要在前 $i \times 2 - 1$ 个当中选择 $i$ 个，可以证明保证从 $2\times x - 1$ 到 $2 \times (x + 1) - 1$ 会同时增加一个左括号和右括号。

所以我们可以用优先队列，从 $1$ 枚举到 $2\times n$，每次枚举到奇数位就将序列中最大的元素累加答案。