【基础算法】贪心 (一) ：简单贪心

一、前言

1. 什么是贪心算法

贪心算法，或者说是贪心策略：企图用局部最优找出全局最优。

1. 把解决问题的过程分成若干步；
2. 解决每⼀步时，都选择 “当前看起来最优的” 解法；
3. “希望” 得到全局的最优解。

示例一：找零问题

假设你是一个小卖部老板，客人从你这里买了一个 4 元的物品，给了你 50 块钱。你手上有足够多的 20、10、5、1 元面额的纸币，你该如何找零，才能使得凑出的纸币的张数最少？

显然，在这个问题中，就是用 [20, 10, 5, 1] 这几种面额的纸币凑出 46 元的最小张数。我们肯定会优先选择 20 元的纸币，肯定不会傻乎乎地全部用 1 元去凑，这是因为我们在选择第一张纸币的时候我们希望尽快地凑满这 46 元，从而达到最小的张数。而这一选择，就是当前看起来最优的解法。当你用 2 张 20 的纸币凑出了 40 元之后，你会选择 5 元的纸币而不是 1 元，因为 5 元也是当前来说更优的解法。最终，你用两张 20 元，一张 5 元，一张 1 元凑出了 46 元，而这也是全局的最优解。

幸运的是，在这道题提供的纸币面额背景下的这种找零策略是正确的，也就是说，对于任何一个数，你都可以利用先选择面额尽可能大的纸币去凑，从而达到最小张数。

---

示例二：最小路径和

假如现在有一个矩阵，每一个格子都对应一个数字。你处于右上角，你需要从右上角到达右下角，问如何走才能使得经过的数字之和最小？

我们可以考虑用贪心试试，即我们每次走都选择当前看起来最优的解法。那么对于贪心来说，从 1 开始，肯定会选择往下走的 2 而不是 4，因为显然 2 更优。再从 2 走，发现下面的 1 比 7 更好，于是走 1，这样一直走下去，最终贪心的解法得出的数字之和为 15。

但是显然我们会发现，最优解并不是 15，而是 8。

这说明了贪心不一定是正确的，如果一道题你要使用贪心的解法，那么你一定要说明贪心的正确性，即严格的证明。

---

证明：找零问题

那么为什么找零问题的贪心解法就是正确的呢？我们这就来证明以下。

这还需要证吗，这不显而易见吗？肯定先选大的面额呀。那么我们来看看这个例子：

纸币的面额为 [1, 7, 10, 20]，用最少的张数凑出 46 元。

如果还是按照贪心的话，用 2 张 20 元凑出 40 元之后，只能选择 6 张 1 元的纸币，一共用 8 张。但是如果我用 1 张 20 元，1 张 10 元，再用 2 张 7 元，2 张 1 元的话，同样是 46 元，这种方案只用了 6 张。这说明我们上面找零策略的正确性是有待商榷的。

证明：

假设使用贪心的解法不是最优解。那么设最优解使用的 [20, 10, 5, 1] 元对应的张数为 [A, B, C, D] 张。此时可以得出以下结论：
$$B\le 1,C\le 1,D\le 4$$
为什么呢？先来说 B。假设在找零的过程中 B 用了 2 张，那么既然是最优解，我必然可以用 1 张 20 元去替代这两张 10 元，去减少我使用的张数。同样的，如果 B 为 3，那么我可以用 1 张 20，1 张 10 去代替。

再来说 C。如果 C = 2，也就是 5 元用了 2 张，那么我何不用 1 张 10 去替换呢？所以 5 元的张数一定不大于 1。D 同理。

现在假设用贪心的解法所使用的 [20, 10, 5, 1] 元对应的张数为 [a, b, c, d] 张。如果我们能够证明出
$$a=A,b=B,c=C,d=D$$
即可说明贪心解就是最优解。

由于贪心解的解法是尽可能多的去用面额大的纸币去凑，直到不能在用为止。因此我们可以得出贪心解所用的 20 元一定是最多的，因此
$$a\ge A$$
但是，假如有
$$a>A$$
成立，那么也就是说我们可以用最优解中的 [B, C, D]张 [10, 5, 1] 去凑出 20 元变成贪心解所用的张数。但事实是我们有
$$B\le 1,C\le 1,D\le 4$$
也就是说它们最多只能凑出 $1\times 10+1\times 5+4\times 1=19$ 元，根本凑不出 20 元。也就证明了 a 不可能大于 A。因此我们可以得到
$$a=A$$
对于
$$b=B,c=C$$
的证明同理。

证毕！

---

2. 贪心算法的特点

• 对于大多数题目，贪心策略的提出并不是很难，难的是证明它是正确的。因为贪心算法相较于暴力枚举，每一步并不是把所有情况都考虑进去，而是只考虑当前看起来最优的情况。但是，局部最优并不等于全局最优，所以我们必须要能严谨的证明我们的贪心策略是正确的。一般证明策略有：反证法，数学归纳法，交换论证法等等。

• 当问题的场景不同时，贪心的策略也会不同。因此，贪心策略的提出是没有固定的套路和模板的。我们后面讲的题目虽然分类，但是大家会发现具体的策略还是相差很大。 因此，不要妄想做几道贪心题目就能遇到一个会一个。有可能做完 100 道贪心题目之后，第 101 道还是没有任何思路。

---

3. 如何学习贪心算法

1. 先有一个认知：做了几十道贪心的题目，遇到一个新的又没有思路，这时很正常的现象，把心态放平。

2. 前期学习的时候，重点放在各种各样的策略上，把各种策略当成经验来吸收。

3. 在平常学习的时候，我们尽可能的证明一下这个贪心策略是否正确，这样有利于培养我们严谨的思维。但是在比赛中，能想出来一个策略就已经不错了，如果再花费大量的时间去证明，有点得不偿失。这个时候，如果根据贪心策略想出来的若干个边界情况都能过的话，就可以尝试去写代码了。

---

二、简单贪心

1. 货仓选址 ⭐

【题目链接】

P10452 货仓选址 - 洛谷

【题目描述】

在一条数轴上有 $N$ 家商店，它们的坐标分别为 $A_1\sim A_N$。

现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。

为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。

【输入格式】

第一行输入整数 $N$。

第二行 $N$ 个整数 $A_1\sim A_N$。

【输出格式】

输出一个整数，表示距离之和的最小值。

【示例一】

输入

4
6 2 9 1

输出

12

【说明/提示】

数据保证，$1\le N\le 100000$，$0\le A_i\le 40000$。

---

(1) 解题思路

这是一个初中的知识点。我们初中就学过，形如
$$|x-a|+|x-b|$$
这样的式子如何求最小值，其实就是数轴上一点到 a 和到 b 的距离之和的最小值。最直观的可以用几何法，即画图来解决，显而易见当 $x$ 在 $a$ 和 $b$ 之间时取最值，答案是 $|a-b|$。也可以采用代数方法，即
$$|x-a|+|x-b|\ge |a-b|$$
这道题目实际上就可以转化成为一个数学公式：
$$\sum _{i=1}^n|x-a_i|$$
其中 $a_i$ 为每家商店到原点的距离，$x$ 为货仓到原点的距离。（设 $a_1 $ 到 $a_n$ 依次递增）
$$\begin{array}{rl}& \sum _{i=1}^n|x-a_i|\\ & \\ & =|x-a_1|+|x-a_2|+\cdots +|x-a_n|\\ & \\ & =(|x-a_1|+|x-a_n|)+(|x-a_2|+|x-a_{n-1}|)+\cdots \end{array}$$
想要这个整体最小，那么我们可以让每个括号都取最小（体现贪心）。
$$\ge |a_1-a_n|+|a_2-a_{n-1}|+\cdots$$
当 $n$ 为偶数时， $x$ 在 $[a_{\frac{n}{2}},a_{\frac{n+1}{2}}]$ 之间的任意位置取等；

当 $n$ 为奇数时， $x$ 在 $ a_{\frac{n + 1}{2}}$ 处取等。

别看上面有那么多推导，看起来很复杂，实际上只需要画一个图便一目了然。

---

(2) 代码实现

#include<iostream>
#include<algorithm>using namespace std;typedef long long LL;const int N = 1e5 + 10;
int a[N];int main()
{int n; cin >> n;for(int i = 1; i <= n; i++) cin >> a[i];sort(a + 1, a + n + 1);int left = 1, right = n;LL dist = 0;while(left <= right){dist += a[right] - a[left];left++;right--;}cout << dist;return 0;
}

---

2. 最大字段和 ⭐⭐

【题目链接】

P1115 最大子段和 - 洛谷

【题目描述】

给出一个长度为 $n$ 的序列 $a$，选出其中连续且非空的一段使得这段和最大。

【输入格式】

第一行是一个整数，表示序列的长度 $n$。

第二行有 $n$ 个整数，第 $i$ 个整数表示序列的第 $i$ 个数字 $a_i$。

【输出格式】

输出一行一个整数表示答案。

【示例一】

输入

7
2 -4 3 -1 2 -4 3

输出

4

【说明/提示】

样例 1 解释

选取 $[3,5]$ 子段 { 3 , − 1 , 2 } \{3, -1, 2\} {3,−1,2}，其和为 $4$。

数据规模与约定

• 对于 $40\%$ 的数据，保证 $n\le 2\times 10^3$。
• 对于 $100\%$ 的数据，保证 $1\le n\le 2\times 10^5$，$-10^4\le a_i\le 10^4$。

---

(1) 解题思路

如果说我们用暴力的解法，就是把所有的子数组全部枚举出来然后求子数组和的最大值。但是这样必定会超时。那么贪心的解法是如何做的呢？

我们发现，在我们从前往后累加的过程中，会遇到以下两种情况：

• 目前的累加和 $\ge 0$，那么我们可以说这一段的累加和能够对后续的累加做出贡献，那么我们就继续往后去累加。
• 如果一旦发现这一段的累加和 $<0$，那么这一段的和就对后续的和做不了贡献，于是我们可以 直接大胆地舍弃掉这一段，再也不去管这一段，之后把累加和重置为 0，继续向后累加。

这样当我们扫描完整个数组一遍之后，就能更新出最大字段和了。

为什么？感觉这种解法有好多情况没考虑进去呀。为什么可以直接舍弃这一段？**难道从这一段中间的某一个数开始的某一个子段和不可能是最大的吗？**接下来我们就来证明这个贪心策略的正确性。

证明：

假如在从 a 点开始累加的过程中第一次出现了一个点 b 使得区间 [a, b] 的区间和 sum[a, b] < 0，贪心的解法是直接舍弃 [a, b] 这一整段，从 b + 1 位置往后开始重新累加。那么我们只需证明，从 [a, b] 中间的任意一个位置开始的某一段的子段和都不可能是最优解即可。

假设在 [a, b] 段中间存在一点 c，使得从 c 开始，到达 d 的一段累加和 sum[c, d] 是最优解。

由于 [a, b]是从 a 开始往后累加过程中第一次出现累加和 $<0$ 的情况，所以一定有 sum[a, c] >= 0。那么一定有 sum[a, d] >= sum[c, d]，这与 sum[c, d] 是最优解矛盾，因此这种情况不存在。

综上，我们就证明了这种贪心策略确实是正确的。

---

(2) 代码实现

#include<iostream>using namespace std;typedef long long LL;const int N = 2e5 + 10;
int a[N];int main()
{int n; cin >> n;for(int i = 1; i <= n; i++) cin >> a[i];LL sum = 0, ans = -0x3f3f3f3f;for(int i = 1; i <= n; i++){sum += a[i];ans = max(ans, sum);  // 更新最大值if(sum < 0) sum = 0;  // 如果这段和小于0，那么重置子段和，从下一个位置开始重新累加}cout << ans;return 0;
}

---

3. 纪念品分组 ⭐

【题目链接】

[P1094 NOIP 2007 普及组] 纪念品分组 - 洛谷

【题目背景】

NOIP2007 普及组 T2

【题目描述】

元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得 的纪念品价值相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪念品， 并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品，乐乐希望分组的数目最少。

你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。

【输入格式】

共 $n+2$ 行：

第一行包括一个整数 $w$，为每组纪念品价格之和的上限。

第二行为一个整数 $n$，表示购来的纪念品的总件数 $G$。

第 $3\sim n+2$ 行每行包含一个正整数 $P_i$ 表示所对应纪念品的价格。

【输出格式】

一个整数，即最少的分组数目。

【示例一】

输入

100 
9 
90 
20 
20 
30 
50 
60 
70 
80 
90

输出

6

【说明/提示】

$50\%$ 的数据满足：$1\le n\le 15$。

$100\%$ 的数据满足：$1\le n\le 3\times 10^4$，$80\le w\le 200$，$5\le P_i\le w$。

---

(1) 解题思路

每组最多只能包括两件纪念品，所以我们肯定不会选择两个价格小的纪念品放在一起，我们希望给定的这个 w 能够充分地被利用。于是我们可以让价格小地物品尽量和价格大的物品凑一块儿这样来分组。

因此，贪心策略就是：尽量让较大的和较小的分到一组，如果不行，那么大的单独一组。

---

(2) 代码实现

#include<iostream>
#include<algorithm>using namespace std;const int N = 3e4 + 10;
int a[N];
int w, n;int main()
{cin >> w >> n;for(int i = 1; i <= n; i++) cin >> a[i];sort(a + 1, a + 1 + n);int left = 1, right = n;int cnt = 0;while(left <= right){while(a[left] + a[right] > w)  // 如果大的不能和小的凑一组，就单独一组{cnt++;right--;}// 出了循环表示这个时候大的和小的可以凑一组left++;right--;cnt++;}cout << cnt;return 0;
}

---

4. 排座椅 ⭐⭐

【题目链接】

[P1056 NOIP 2008 普及组] 排座椅 - 洛谷

【题目描述】

上课的时候总会有一些同学和前后左右的人交头接耳，这是令小学班主任十分头疼的一件事情。不过，班主任小雪发现了一些有趣的现象，当同学们的座次确定下来之后，只有有限的 $D$ 对同学上课时会交头接耳。

同学们在教室中坐成了 $M$ 行 $N$ 列，坐在第 $i$ 行第 $j$ 列的同学的位置是 $(i,j)$，为了方便同学们进出，在教室中设置了 $K$ 条横向的通道，$L$ 条纵向的通道。

于是，聪明的小雪想到了一个办法，或许可以减少上课时学生交头接耳的问题：她打算重新摆放桌椅，改变同学们桌椅间通道的位置，因为如果一条通道隔开了 $2$ 个会交头接耳的同学，那么他们就不会交头接耳了。

请你帮忙给小雪编写一个程序，给出最好的通道划分方案。在该方案下，上课时交头接耳的学生的对数最少。

【输入格式】

第一行，有 $5$ 个用空格隔开的整数，分别是 $M,N,K,L,D(2\le N,M\le 1000,0\le K<M,0\le L<N,0\le D\le 2000)$。

接下来的 $D$ 行，每行有 $4$ 个用空格隔开的整数。第 $i$ 行的 $4$ 个整数 $X_i,Y_i,P_i,Q_i$，表示坐在位置 $(X_i,Y_i)$ 与 $(P_i,Q_i)$ 的两个同学会交头接耳（输入保证他们前后相邻或者左右相邻）。

输入数据保证最优方案的唯一性。

【输出格式】

共两行。
第一行包含 $K$ 个整数 $a_1,a_2,\dots ,a_K$，表示第 $a_1$ 行和 $a_1+1$ 行之间、第 $a_2$ 行和 $a_2+1$ 行之间、…、第 $a_K$ 行和第 $a_K+1$ 行之间要开辟通道，其中 $a_i<a_{i+1}$，每两个整数之间用空格隔开（行尾没有空格）。

第二行包含 $L$ 个整数 $b_1,b_2,\dots ,b_L$，表示第 $b_1$ 列和 $b_1+1$ 列之间、第 $b_2$ 列和 $b_2+1$ 列之间、…、第 $b_L$ 列和第 $b_L+1$ 列之间要开辟通道，其中$b_i<b_{i+1}$，每两个整数之间用空格隔开（列尾没有空格）。

【示例一】

输入

4 5 1 2 3
4 2 4 3
2 3 3 3
2 5 2 4

输出

2
2 4

【说明/提示】

上图中用符号*、※、+标出了 $3$ 对会交头接耳的学生的位置，图中 $3$ 条粗线的位置表示通道，图示的通道划分方案是唯一的最佳方案。

2008 年普及组第二题

---

(1) 解题思路

由于横纵通道的数量有限，那么我们希望在这有限的通道中阻止尽可能多的同学交头接耳。那么我们可以记录对于每一个横纵通道，它可以阻止的学生数，然后从大到小排序并输出前 l 和 k 个，找到这几个通道即可。

但是我们需要输出的是通道的位置，而不是它能阻止的学生数。如果我们单纯按照能阻止的学生数来排序过后，就会丢失通道原来的下标。因此我们可以创建一个下标数组 index，重写排序规则，对这个下标数组进行排序。而由于我们要按从小到大的顺序输出通道的位置，因此我们还需要对这个下标数组进行排序。

---

(2) 代码实现

#include<iostream>
#include<algorithm>using namespace std;const int N = 1010;
int r[N], c[N];  // 记录通道能阻止的学生数
int index_r[N], index_c[N];  // 下标数组
int m, n, k, l, d;// 按照下标对应的能阻止的学生数进行排序
bool cmp_r(int a, int b){ return r[a] > r[b]; }
bool cmp_c(int a, int b){ return c[a] > c[b]; }int main()
{cin >> m >> n >> k >> l >> d;for(int i = 1; i <= d; i++){int x, y, p, q;cin >> x >> y >> p >> q;// 需要放纵向通道if(x == p) c[min(y, q)]++;// 需要放横向通道if(y == q) r[min(x, p)]++;}// 初始化下标数组for(int i = 1; i <= N; i++) index_r[i] = i;for(int i = 1; i <= N; i++) index_c[i] = i;// 第一次排序：根据能阻止的学生数进行排序sort(index_r + 1, index_r + m + 1, cmp_r);sort(index_c + 1, index_c + n + 1, cmp_c);// 第二次排序：为了从小到大输出通道位置sort(index_r + 1, index_r + k + 1);sort(index_c + 1, index_c + l + 1);// 输出横向通道for(int i = 1; i <= k; i++) cout << index_r[i] << " ";cout << endl;// 输出纵向通道for(int i = 1; i <= l; i++) cout << index_c[i] << " ";return 0;
}

---

5. 矩阵消除游戏 ⭐⭐⭐

【题目链接】

矩阵消除游戏

---

(1) 解题思路

这道题乍一看，我们容易想到一种思路就是统计每行每列的和，选取最大的那一行/列，选完之后更新每行每列的值，再选取最大的那一个，重复进行。但是，这样贪心是有问题的，比如下面这个例子：

100  9  100   0   0
100  0  10k = 2

按照我们上面所说的方法，应该选第一列和第三列，但是实际上最大的选法应该是选第一行和第三行。这种贪心策略错误的根本原因就在于这道题中行 (列) 的选择是会影响其他列 (行) 的结果的。它不像上一道题一样，横纵通道之间互不影响。所以我们应该换一种思路。

仔细观察数据范围可以发现，矩阵的大小最大也就 15，很小。因此我们可以采用枚举的思路，我们可以枚举每一行选或者不选，然后再根据行的选择情况去贪心地选列。而行的美枚举方式可以采用二进制枚举。

---

(2) 代码实现

#include<iostream>
#include<cstring>
#include<algorithm>using namespace std;const int N = 20;
int mat[N][N];
int col[N];  // 记录每一列的和
int n, m, k;// 计算一个二进制数中有多少个 1，即选了多少个行
int calc(int st)
{int cnt = 0;for(int i = 0; i < n; i++){if((st >> i) & 1) cnt++;}return cnt;
}int main()
{cin >> n >> m >> k;for(int i = 1; i <= n; i++)for(int j = 1; j <= m; j++)cin >> mat[i][j];int ans = 0;  // 最终结果for(int st = 0; st < (1 << n); st++)  // 枚举行的选择情况{int cnt = calc(st);if(cnt > k) continue;  // 如果选的行太多了，就跳过这种情况memset(col, 0, sizeof(col));  // 每一种情况算列的和之前，先清空上一轮的数据int sum = 0;  // 当前这种情况的总和for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){// 如果当前这一行的这一位被选了，那么加在总和里if((st >> (i - 1)) & 1) sum += mat[i][j];// 否则加在列的和中else col[j] += mat[i][j];}}sort(col + 1, col + 1 + m, greater<int>());int t = min(k - cnt, m);  // 防止越界访问for(int i = 1; i <= t; i++) sum += col[i];ans = max(ans, sum);}cout << ans;return 0;
}