算法基础篇：（八）贪心算法之简单贪心：从直觉到逻辑的实战指南
前言 在算法的世界里，有一类算法如同生活中的 “即时决策派”—— 不纠结于未来的所有可能性，只专注于当下的最优选择，这就是贪心算法。它看似简单直观，甚至有些 “鲁莽”，却能高效解决一大批经典问题。但贪心算法也是出了名的 “两极分化”：简单题能让你觉得 “理所当然”，难题却能让你怀疑人生。今天我们就聚焦贪心算法的入门核心 —— 简单贪心，通过经典例题拆解其思想、逻辑证明和代码实现，帮你从 “知其然” 到 “知其所以然”，真正掌握这份 “当下最优” 的智慧。下面就让我们正式开始吧！
一、贪心算法是什么？—— 不止是 “鼠目寸光”1.1 贪心的核心思想 贪心算法，本质上是一种 “局部最优导向全局最优” 的策略。它将复杂问题拆分成一系列连续的子问题，在每个子问题中都做出当前看起来最优的选择，并且不回溯、不反悔，最终希望通过这些局部最优解的累积得到全局最优解。
举个生活中的例子：你要从家到公司，想最快到达。贪心策略就是：每个路口都选择当前路况最好、距离最近的路线，而不是提前规划全程所有可能路径 —— 这种 “走一步看一步” 的决策方式，正是贪心的核心。
但这里有个关键前提：并非所有问题都能用贪心解决。只有当问题满足 “局部最优解的累积必然导致全局最优解” 时，贪心才有效。这也是贪心算法的难点所在：策略的提出不难，难的是证明它是正确的。
1.2 贪心算法的三大特点无后效性：每个子问题的决策只依赖当前状态，不影响之前的决策，也不被之前的决策所影响。贪心选择性质：全局最优解可以通过一系列局部最优解（贪心选择）得到。无固定模板：与动态规划有明确的状态转移方程不同，贪心策略需要根据具体问题场景设计，没有通用的套路可循。1.3 学习贪心的正确姿势 很多初学者会有困惑：为什么做了几十道贪心题，遇到新题还是没思路？其实这是正常现象！贪心的灵活性决定了它需要大量的题型积累和逻辑训练。学习时要注意以下几点：
前期重点吸收各种题型的贪心策略，把它们当成 “经验库”；尽量尝试证明策略的正确性（常用反证法、数学归纳法、交换论证法），培养严谨思维；比赛中无需过度纠结证明：如果策略能通过几个边界情况，就可以大胆尝试编码。二、经典例题实战 —— 简单贪心的 5 个核心场景 下面我们通过 5 道经典例题，拆解简单贪心的常见场景、策略设计和代码实现。每道题都会从 “题目分析→贪心策略→逻辑证明→代码实现” 四个维度展开，帮你吃透核心逻辑。
例题 1：货仓选址（洛谷 P10452）—— 中位数的魔力题目链接：https://www.luogu.com.cn/problem/P10452
题目描述 在一条数轴上有 n 家商店，坐标分别为 a₁, a₂, ..., aₙ。现在要在数轴上建立一家货仓，求货仓建在何处，能使货仓到所有商店的距离之和最小。
输入：第一行 n，第二行 n 个整数表示商店坐标（n≤1e5，aᵢ≤1e6）
输出：距离之和的最小值
示例输入：46 2 9 1
示例输出：12
题目分析 这是一道典型的 “一维选址” 问题。直观上，我们可能会想到 “平均值”—— 毕竟平均值是数据的中心。但实际上，中位数才是最优解。为什么？
贪心策略
将所有商店坐标从小到大排序；货仓建在中位数位置： 若 n 为奇数，选第 (n+1)/2 个位置；若 n 为偶数，选第 n/2 到第 n/2+1 个位置之间的任意点（距离和相同）。逻辑证明（反证法） 假设货仓建在非中位数位置 x，中位数为 m。我们证明将 x 移到 m 会使距离和减小：
设排序后的坐标为 a₁≤a₂≤...≤aₙ，中位数 m=a [k]（k=(n+1)/2）。
若 x>m：此时在 m 左侧有 k 家商店，右侧有 n-k 家商店（n-k≤k）。将 x 向左移动 1 单位，左侧商店的总距离增加 1×k，右侧商店的总距离减少 1×(n-k)，总距离变化为 k-(n-k)=2k-n≥0（因为 k≥n/2），即总距离减小或不变。若 x 代码实现代码语言：javascript复制#include #include using namespace std; typedef long long LL; const int N = 1e5 + 10; int n; LL a[N]; int main() { cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; sort(a + 1, a + 1 + n); LL ret = 0; // 利用结论计算：(a[n]-a[1]) + (a[n-1]-a[2]) + ... for (int i = 1; i <= n / 2; i++) { ret += a[n - i + 1] - a[i]; } cout << ret << endl; return 0; }拓展结论 对于公式 sum=\sum |a [i]-x|（i=1 到 n），当 x 取数组的中位数时，sum 取得最小值。这个结论在后续的贪心、动态规划问题中会频繁用到，一定要牢记！ 例题 2：最大子段和（洛谷 P1115）—— 果断舍弃 “负资产”题目链接：https://www.luogu.com.cn/problem/P1115 题目描述 给出一个长度为 n 的序列 a，选出其中连续且非空的一段，使得这段的和最大。 输入：第一行 n，第二行 n 个整数（1≤n≤2e5，-1e4≤aᵢ≤1e4） 输出：最大子段和 示例输入：72 -4 3 -1 2 -4 3 示例输出：4（对应子段 [3,-1,2]） 题目分析 这道题是贪心算法的经典应用，也是面试高频题。核心矛盾是：当当前累积和为负数时，是否要舍弃前面的子段？ 贪心策略 从前往后遍历序列，维护一个当前累积和 sum 和最大子段和 ret： 每次将当前元素加入 sum；更新 ret 为 ret 和 sum 中的较大值；若 sum<0：说明当前子段对后续累加毫无贡献（甚至会拖后腿），直接将 sum 重置为 0，从下一个元素重新开始累积。逻辑证明（反证法） 我们需要证明：当 sum<0 时，舍弃当前子段是最优选择。 假设存在一段区间 [a,b]，其和 sum [a,b]<0。若不舍弃这段区间，后续存在子段 [b+1,c]，使得 sum [a,c] 是最大子段和。但 sum [a,c] = sum [a,b] + sum [b+1,c] < sum [b+1,c]，这与 sum [a,c] 是最大子段和矛盾。因此，舍弃 sum<0 的子段不会错过最优解。 进一步证明：区间内不存在比当前起点更优的起点。假设区间 [a,b] 中存在点 c（a 代码实现代码语言：javascript复制#include using namespace std; typedef long long LL; const int N = 2e5 + 10; int n; LL a[N]; int main() { cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; LL sum = 0, ret = -1e6; // ret初始化为最小值，应对全负序列 for (int i = 1; i <= n; i++) { sum += a[i]; ret = max(ret, sum); if (sum < 0) sum = 0; // 舍弃负资产 } cout << ret << endl; return 0; }注意点 初始时 ret 要设为极小值（如 - 1e6），而不是 0—— 因为序列可能全为负数，此时最大子段和是最大的那个负数。时间复杂度 O (n)，空间复杂度 O (1)，是该问题的最优解法。例题 3：纪念品分组（洛谷 P1094）—— 双指针的 “配对艺术”题目链接：https://www.luogu.com.cn/problem/P1094 题目描述 元旦晚会要发放纪念品，每组最多 2 件，且每组总价格不超过 w。求最少的分组数目。 输入：第一行 w（每组价格上限），第二行 n（纪念品总数），后续 n 行是每件纪念品的价格（1≤n≤3e4，80≤w≤200，5≤pᵢ≤w） 输出：最少分组数 示例输入：1009902020305060708090示例输出：6 题目分析 要使分组数最少，核心思路是 “尽可能让每件纪念品都和其他纪念品配对”，避免单独分组。最优策略是让 “最便宜的和最贵的配对”—— 如果两者之和不超过 w，就配对；否则最贵的只能单独分组（因为它无法和任何其他纪念品配对）。 贪心策略 将所有纪念品价格从小到大排序；用双指针 l（指向当前最便宜的）和 r（指向当前最贵的）；若 a [l]+a [r]≤w：配对成功，l++，r--，分组数 + 1；若 a [l]+a [r]>w：最贵的单独分组，r--，分组数 + 1；重复直到 l>r。逻辑证明（交换论证法） 交换论证法的核心是：假设存在最优解，通过交换其中的元素，证明最优解可以转化为贪心解，从而说明贪心解是最优的。 假设最优解中，存在一组配对方式与贪心策略不同： 情况 1：a [r]（当前最贵）单独分组。贪心解中 a [r] 单独分组，最优解中 a [r] 也必须单独分组（因为没有比 a [l] 更便宜的纪念品能和它配对），两者一致。情况 2：a [l]+a [r]≤w，但最优解中 a [l] 与 a [k]（k 代码实现代码语言：javascript复制#include #include using namespace std; const int N = 3e4 + 10; int w, n; int a[N]; int main() { cin >> w >> n; for (int i = 1; i <= n; i++) cin >> a[i]; sort(a + 1, a + 1 + n); int l = 1, r = n, ret = 0; while (l <= r) { if (a[l] + a[r] <= w) { l++; r--; } else { r--; } ret++; } cout << ret << endl; return 0; }优化点排序后用双指针遍历，时间复杂度 O (nlogn)（主要消耗在排序），对于 n=3e4 完全适用；无需额外空间存储分组，直接通过指针移动计数，空间复杂度 O (1)。例题 4：排座椅（洛谷 P1056）—— 贪心的 “优先级选择”题目链接：https://www.luogu.com.cn/problem/P1056 题目描述 教室有 M 行 N 列座位，有 D 对同学会交头接耳（前后或左右相邻）。要设置 K 条横向通道和 L 条纵向通道，使交头接耳的同学对数最少。通道会隔开相邻的行或列，从而阻止这对同学交头接耳。 输入：第一行 M、N、K、L、D，后续 D 行是交头接耳的同学坐标（2≤M,N≤1e3，0≤K 输出：第一行 K 个横向通道的位置，第二行 L 个纵向通道的位置（按升序排列） 示例输入：4 5 1 2 34 2 4 32 3 3 32 5 2 4 示例输出：22 4 题目分析 核心观察：横向通道只影响前后相邻的同学，纵向通道只影响左右相邻的同学。因此，横向和纵向通道的设置是独立的，可以分开处理。 对于横向通道：我们需要选择 K 个位置，使每个位置能隔开的交头接耳对数最多；纵向通道同理。这是一种 “选最大收益” 的贪心策略。 贪心策略 分别统计每个横向位置（第 i 行和第 i+1 行之间）能隔开的交头接耳对数；分别统计每个纵向位置（第 j 列和第 j+1 列之间）能隔开的交头接耳对数；对横向位置按 “收益”（隔开的对数）降序排序，选前 K 个；对纵向位置按 “收益” 降序排序，选前 L 个；将选中的位置按升序排列后输出。逻辑证明 由于我们选择的是收益最大的 K 个横向位置和 L 个纵向位置，不存在其他选择能隔开更多的交头接耳对数。因此，这种 “选最大收益” 的策略必然是最优的。 代码实现代码语言：javascript复制#include #include using namespace std; const int N = 1010; struct Node { int index; // 通道位置（第index行/列和index+1之间） int cnt; // 能隔开的交头接耳对数 } row[N], col[N]; // 按收益降序排序 bool cmp1(Node& x, Node& y) { return x.cnt > y.cnt; } // 按位置升序排序 bool cmp2(Node& x, Node& y) { return x.index < y.index; } int main() { int m, n, k, l, d; cin >> m >> n >> k >> l >> d; // 初始化：每个位置的index就是其本身 for (int i = 1; i <= m; i++) row[i].index = i; for (int i = 1; i <= n; i++) col[i].index = i; while (d--) { int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; if (x1 == x2) { // 左右相邻，统计纵向通道 int pos = min(y1, y2); col[pos].cnt++; } else { // 前后相邻，统计横向通道 int pos = min(x1, x2); row[pos].cnt++; } } // 选择收益最大的K个横向通道和L个纵向通道 sort(row + 1, row + 1 + m, cmp1); sort(col + 1, col + 1 + n, cmp1); // 按位置升序排列 sort(row + 1, row + 1 + k, cmp2); sort(col + 1, col + 1 + l, cmp2); // 输出横向通道 for (int i = 1; i <= k; i++) { cout << row[i].index << " "; } cout << endl; // 输出纵向通道 for (int i = 1; i <= l; i++) { cout << col[i].index << " "; } cout << endl; return 0; }注意点通道位置是 “第 index 行 / 列和 index+1 之间”，因此统计时要取 min (x1,x2) 或 min (y1,y2)；最终输出需要按位置升序排列，符合题目要求。例题 5：矩阵消除游戏（牛客网）—— 贪心 + 枚举的 “组合拳”题目链接：https://ac.nowcoder.com/acm/problem/200190 题目描述 n 行 m 列的矩阵，每个单元格有一个权值。进行 k 个回合，每个回合可选择一行或一列，将其所有单元格权值变为 0，并获得该行列的权值和。求最大得分。 输入：第一行 n、m、k，后续 n 行 m 列整数（1≤n,m≤15，1≤aᵢⱼ≤1e6，1≤k≤n*m） 输出：最大得分 示例输入：3 3 2101 1 1021 202 1100 8 100 示例输出：414（选择第一列和第三列，和为 101+1+100 + 102+1+100 = 414） 题目分析 这道题很容易陷入 “贪心陷阱”：每次选择当前权值和最大的行或列。但这种策略是错误的 —— 因为选择一行后，会影响后续列的权值和（该行的列元素会变为 0），反之亦然。 例如： 代码语言：javascript复制100 9 10 0 0 0 100 0 10 当k=2 时，贪心会选第一列（和 200）和第三列（和 20），总得分 220；但最优解是选第一行（和 119）和第三行（和 110），总得分 229。 因此，这道题需要 “贪心 + 枚举” 的组合策略：先枚举所有可能的行选择，再对列进行贪心选择。 贪心策略 枚举所有行的选择情况（因为 n≤15，总共有 2¹⁵=32768 种情况，可行）；对于每种行选择（选 t 行）： 计算选中行的权值和；计算剩余列的权值和（未被选中的行的列元素和）；从剩余列中选择 k-t 个权值和最大的列，累加得分；所有情况中取最大得分。逻辑证明 由于 n 和 m 很小，枚举所有行选择是可行的。对于每种行选择，列的选择必然是贪心选最大的 —— 因为列之间是独立的（选择一列不会影响其他列的权值和），因此 “选最大的 k-t 列” 是最优的。 代码实现代码语言：javascript复制#include #include #include using namespace std; const int N = 20; int n, m, k; int a[N][N]; int col[N]; // 存储每列的权值和 // 统计x的二进制中1的个数（选中的行数） int count_one(int x) { int ret = 0; while (x) { ret++; x -= x & -x; // 消除最低位的1 } return ret; } // 按权值和降序排序 bool cmp(int a, int b) { return a > b; } int main() { cin >> n >> m >> k; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> a[i][j]; } } int max_score = 0; // 枚举所有行选择情况（st的二进制位表示是否选该行） for (int st = 0; st < (1 << n); st++) { int selected_rows = count_one(st); if (selected_rows > k) continue; // 选的行数超过k，跳过 int remaining_cols = k - selected_rows; // 还能选的列数 memset(col, 0, sizeof col); int score = 0; // 计算选中行的得分和剩余列的权值和 for (int i = 0; i < n; i++) { if (st >> i & 1) { // 该行被选中 for (int j = 0; j < m; j++) { score += a[i][j]; } } else { // 该行未被选中，累加列权值和 for (int j = 0; j < m; j++) { col[j] += a[i][j]; } } } // 选择剩余列中权值和最大的remaining_cols个 sort(col, col + m, cmp); for (int i = 0; i < remaining_cols; i++) { score += col[i]; } max_score = max(max_score, score); } cout << max_score << endl; return 0; }优化点用二进制枚举行选择，能够高效遍历所有可能；列的权值和计算可以通过预处理优化，但由于 n 和 m 很小，直接计算也完全可行；时间复杂度 O (2ⁿ × m log m)，对于 n=15、m=15，2¹⁵=32768，m log m≈50，总运算量约 1.6e6，效率很高。三、简单贪心的常见策略总结 通过上面的例题，我们可以总结出简单贪心的几种常见策略模板，帮你快速应对同类问题： 1. 排序 + 选择类核心思路：先排序，再根据问题选择 “最小 / 最大”、“中位数” 等关键位置。适用场景：货仓选址（中位数）、纪念品分组（双指针配对）、最大子段和（排序后贪心选择，本题未用排序但属于选择类）。技巧：排序后常用双指针、遍历等方式进行贪心选择。2. 收益最大化类核心思路：计算每个选择的 “收益”，优先选择收益最大的。适用场景：排座椅（通道位置的收益是隔开的对数）、矩阵消除游戏（列的收益是权值和）。技巧：用数组统计收益，排序后选择前 k 个。3. 舍弃负资产类核心思路：当当前累积的结果为负时，果断舍弃，重新开始。适用场景：最大子段和（sum<0 时重置）、股票买卖（LeetCode 121，当当前价格低于买入价时重新买入）。技巧：维护一个累积变量，实时更新最优结果，负累积时重置。4. 枚举 + 贪心类核心思路：当直接贪心有陷阱时，枚举部分选择，再对剩余部分贪心。适用场景：矩阵消除游戏（枚举行选择，贪心选列）。技巧：枚举的维度要小（如 n≤15），否则会超时。四、贪心算法的常见误区与避坑指南1. 误区 1：认为 “贪心就是选最大 / 最小” 很多初学者会误以为贪心就是简单地选最大或最小，但实际上贪心策略是根据问题场景设计的。例如货仓选址选的是中位数，而不是最大或最小；最大子段和是舍弃负累积，而不是选最大的元素。 2. 误区 2：不证明策略正确性，直接编码 贪心算法的正确性不是直觉能保证的。例如矩阵消除游戏的 “选当前最大” 策略看似正确，实则有反例。因此，即使是简单贪心，也要尽量通过反证法、交换论证法等验证策略。 3. 误区 3：忽视边界情况全负序列的最大子段和（需初始化为极小值）；纪念品分组中 n=1 的情况（必须单独分组）；矩阵消除游戏中 k≥n+m 的情况（选所有行和列）。4. 避坑指南遇到贪心问题，先尝试构造反例：如果能找到反例，说明策略错误；若无法构造反例，再尝试证明策略的正确性；编码时优先处理边界情况，再处理一般情况；对于数据量较大的问题（如 n≤1e5），优先选择 O (n) 或 O (n log n) 的贪心策略。总结 贪心算法是一种 “当下最优” 的决策艺术，它不需要复杂的状态转移，却能高效解决很多问题。简单贪心作为入门基础，核心在于 “排序 + 选择”、“收益最大化”、“舍弃负资产” 等策略，而难点在于策略的设计和正确性证明。 学习贪心算法，不要急于求成，要通过大量例题积累经验，培养 “贪心直觉”。记住：贪心没有固定模板，但有通用思路 —— 将问题拆分成子问题，每个子问题做出局部最优选择，并且证明这些选择能累积成全局最优。 当你能熟练解决简单贪心问题后，就可以进阶到更复杂的贪心问题（如哈夫曼编码、区间调度、推公式类贪心，这些我在后续的博客中会为大家详解），逐步构建完整的贪心算法知识体系。 最后，算法学习的核心是 “理解 + 实践”。希望这篇文章能帮你打开贪心算法的大门，多动手编码、多思考证明，你会发现贪心算法的魅力所在！