博客详情 - DL24JPOJ

DL24JP 的博客
贪心算法入门：用"眼前的智慧"解决问题
DL24JP SU @ 2026-6-17 19:04:26

适合阅读：初中阶段学习信息学竞赛的同学

例题来源：信息学奥赛一本通（C++版），含 NOIP 真题

一、什么是贪心算法？

想象你在爬山，雾很大，看不清远处。你只知道：每一步都往最高的方向走，最后就能到达山顶。这就是贪心算法的核心思想——

每一步都做出"当前看起来最好"的选择，不回头、不后悔。

用正式的话说：贪心算法在每一步选择中都采取"当前最优策略"，不看未来，只看眼前，希望通过每一步的局部最优，最终达到全局最优。

两个关键问题

拿到一个问题，想用贪心算法，必须先想清楚两件事：

贪心策略是什么？ —— 每一步该怎么选？按什么规则选？
这个策略对吗？ —— 局部最优能不能保证全局最优？

⚠️ 贪心算法不是万能药。很多问题"看起来"能用贪心，实际上却是错的。所以学会证明贪心策略的正确性，才是掌握这个算法的关键。

常见套路

排序 —— 把数据按某种规则排序，然后按顺序处理
每次选最优 —— 在候选中挑一个"最好的"
维护一个集合 —— 用最小的代价维护当前状态

下面通过 6 个经典例题，手把手带你掌握贪心算法。

二、例题精讲

例6.1 排队接水 —— "快的先来"

题目描述

有 $n$ 个人在一个水龙头前排队接水，第 $i$ 个人的接水时间为 $T_i$ 。请编程找出一种排队顺序，使得 $n$ 个人的平均等待时间最小。

输入格式

第一行：整数 $n$ （ $1 \le n \le 1000$ ）
第二行： $n$ 个整数 $T_1, T_2, \dots, T_n$ ，表示每个人的接水时间，空格分隔

输出格式

第一行：一种排队顺序，即 $1$ 到 $n$ 的一种排列（输出原始编号）
第二行：该排列方案下的平均等待时间（保留两位小数）

样例输入

10
56 12 1 99 1000 234 33 55 99 812

样例输出

3 2 7 8 1 4 9 6 10 5
291.90

样例解释

输入有 10 个人，接水时间依次为 56, 12, 1, 99, 1000, 234, 33, 55, 99, 812。按接水时间从小到大排序后，顺序为：第3人(1) → 第2人(12) → 第7人(33) → 第8人(55) → 第1人(56) → 第4人(99) → 第9人(99) → 第6人(234) → 第10人(812) → 第5人(1000)。计算平均等待时间为 291.90。

贪心策略

接水时间短的人排在前面，接水时间长的人排在后面。即按 $T_i$ 从小到大排序。

为什么对？

假设有两个人，接水时间分别是 3 和 10：

3 在前：第一个人等 0，第二个人等 3，总等待 = 3
10 在前：第一个人等 0，第二个人等 10，总等待 = 10

显然快的人在前面，慢的人等的时间就短。推广到 $n$ 个人：如果排队顺序中有一个"时间长的排在时间短的前面"，交换这两个人的位置，总等待时间一定会减少。所以从小到大排列就是最优解。

解题思路

把每个人封装成结构体，记录原始编号和接水时间
按接水时间升序排序
遍历排序后的数组，第 $i$ 个人的等待时间 = 前面所有人的接水时间之和
累计总等待时间，最后除以 $n$ 得到平均值

🔑 关键技巧：用 wait 变量记录"前面已接完的人总共花了多长时间"，每处理一个人就累加。

C++ 代码

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;

struct Person {
    int id;   // 原始编号
    int time; // 接水时间
} a[1005];

bool cmp(Person x, Person y) {
    return x.time < y.time;  // 按接水时间升序
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].time;
        a[i].id = i;
    }
    sort(a + 1, a + n + 1, cmp);

    long long total = 0;  // 总等待时间（可能很大，用long long）
    long long wait = 0;   // 当前已累计的接水时间
    for (int i = 1; i <= n; i++) {
        cout << a[i].id << " ";
        total += wait;        // 第i个人要等"前面所有人接完"
        wait += a[i].time;    // 自己接水的时间累加入wait
    }
    cout << endl;
    printf("%.2f\n", (double)total / n);
    return 0;
}

代码说明

要点	说明
`cmp` 函数	排序规则：`time` 小的在前
`wait` 变量	记录"在我之前的人总共花了多少时间"，每轮先加到 `total` 再更新
`long long`	总等待时间可能超出 int 范围（1000人×每人可能很大），用 64 位整数
`printf("%.2f")`	保留两位小数输出平均值

例6.2 均分纸牌（NOIP2002）—— "多了给隔壁，少了问隔壁要"

题目描述

有 $n$ 堆纸牌，编号 $1, 2, \dots, n$ 。每堆上有若干张，但纸牌总数必为 $n$ 的倍数。可以在任一堆上取若干张纸牌移动，规则如下：

第 1 堆的牌，只能移到第 2 堆
第 $n$ 堆的牌，只能移到第 $n-1$ 堆
其余堆的牌，可以移到相邻左边或右边的堆上

求用最少的移动次数使每堆纸牌数都相等。

输入格式

第一行： $n$ （ $1 \le n \le 100$ ）
第二行： $a_1, a_2, \dots, a_n$ （ $1 \le a_i \le 10000$ ）

输出格式

一个整数，表示最少移动次数

样例输入

4
9 8 17 6

样例输出

样例解释

总共 40 张牌，平均每堆 10 张。移动过程：

从第 3 堆移 4 张到第 4 堆 → 9 8 13 10
从第 3 堆移 3 张到第 2 堆 → 9 11 10 10
从第 2 堆移 1 张到第 1 堆 → 10 10 10 10

共 3 次移动。

贪心策略

从左到右依次处理：如果当前堆不等于平均值，就把差值（多出或缺少的牌）一次性移到右边那堆，计数 +1。

为什么对？

关键洞察：第 1 堆只能和第 2 堆交换纸牌。所以第 1 堆要达到平均值，必须且只能通过第 2 堆来调整。

把第 1 堆搞定后，问题就变成了 $n-1$ 堆的子问题（第 2 ~ $n$ 堆）。而第 2 堆现在变成了新的"第 1 堆"（只能和第 3 堆交换）。以此类推，每一步都是唯一的、无可避免的，所以贪心策略一定正确。

💡 这其实是"递推"思想：把大问题一步步缩小成小问题。

解题思路

计算总和 $sum$ 和平均值 $avg = sum / n$
遍历第 1 ~ $n-1$ $n - 1$ 堆：
- 如果 $a[i] \neq avg$ ，则 $a[i+1] \;+\!\!=\; (a[i] - avg)$ ， $a[i] = avg$ ，答案 +1
前 $n-1$ 堆调好后，第 $n$ 堆自然就等于 $avg$ 了（因为总和是 $n \times avg$ ）

C++ 代码

#include <iostream>
using namespace std;

int a[105];

int main() {
    int n, sum = 0;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum += a[i];
    }
    int avg = sum / n;   // 每堆的目标数量
    int ans = 0;

    for (int i = 1; i < n; i++) {
        if (a[i] != avg) {
            a[i + 1] += (a[i] - avg);  // 差值全部移给右边
            a[i] = avg;                // 当前堆达成目标
            ans++;                     // 计一次移动
        }
    }
    cout << ans << endl;
    return 0;
}

代码说明

要点	说明
`a[i] - avg`	正数 = 多了要移出，负数 = 少了要从右边取（"借"）
`a[i+1] += (a[i]-avg)`	无论正负，右堆直接加上差值即可
只遍历到 `n-1`	前 n-1 堆调整完，第 n 堆自动等于平均值

例6.3 删数问题（NOIP1994）—— "删掉第一个山峰"

题目描述

输入一个高精度正整数 $n$ （ $n$ 不超过 240 位），去掉其中任意 $s$ 个数字后，剩下的数字按原左右次序组成一个新的正整数。请找出使得新数最小的方案，输出这个新数。

输入格式

第一行：正整数 $n$ （字符串形式，不超过 240 位）
第二行：整数 $s$ （要删除的数字个数）

输出格式

一行：删除后剩下的最小正整数（不含前导零）

样例输入

175438
4

样例输出

样例解释

原数 175438，删除 4 个数字。

删 7 → 15438
删 5 → 1438
删 4 → 138
删 8 → 13

最终得到最小数 13。

贪心策略

从左往右找第一个"山峰"——当前位数字大于后一位数字的地方，删掉当前位。重复 $s$ 次。

更高效的做法（单调栈）：遍历每一位数字，如果栈顶数字比当前数字大，就弹栈（相当于删除栈顶），直到删除次数用完或栈顶不比当前数字大。

为什么对？

想让一个数尽可能小，高位越小越好。从左往右扫描，如果发现某个数字比它后面的数字大，删掉它就能让后面更小的数字"顶上来"占高位，从而使整个数变小。这就是每次找并删除第一个逆序对的原因。

解题思路

用字符串 ans 作为"单调栈"（存最终结果）
遍历原数的每一位 c：
- 当还能删（ $s>0$ ）、栈非空、且栈顶 > c 时，弹栈， $s$ 减 1
- 将 c 压入栈
遍历完后如果还没删够 $s$ 个，从末尾删除剩余次数
去除前导零后输出（注意至少保留一位数字）

C++ 代码

#include <iostream>
#include <string>
using namespace std;

int main() {
    string n;
    int s;
    cin >> n >> s;

    string ans;  // 用 string 模拟单调栈
    for (char c : n) {
        // 栈顶比当前数字大时可以删掉栈顶
        while (s > 0 && !ans.empty() && ans.back() > c) {
            ans.pop_back();
            s--;
        }
        ans.push_back(c);
    }
    // 如果还没删够 s 个，从末尾删除（此时序列单调不减）
    while (s > 0 && !ans.empty()) {
        ans.pop_back();
        s--;
    }
    // 去除前导零
    int pos = 0;
    while (pos < (int)ans.size() - 1 && ans[pos] == '0') pos++;
    cout << ans.substr(pos) << endl;
    return 0;
}

代码说明

要点	说明
`ans` 模拟单调栈	维护一个非递减的数字序列
`ans.back() > c`	发现"山峰"，弹栈即删除
末尾删除	如果删完所有山峰还不够 $s$ 个，序列已经是单调不减的，从尾巴删最划算
去前导零	`pos` 跳过连续 `'0'`，但 `ans.size()-1` 保证至少输出一个字符（如全删只剩 `"0"`）

例6.4 拦截导弹问题（NOIP1999）—— "用最少的系统接住所有导弹"

题目描述

某国开发出一种导弹拦截系统，但有一个缺陷：第一发炮弹可以到达任意高度，之后每一发炮弹都不能高于前一发的高度（即高度非递增）。

某天，雷达捕捉到敌国的 $n$ 枚导弹依次飞来的高度。由于系统还在试用阶段，一套系统可能无法拦截所有导弹。请计算最少需要配备多少套这种拦截系统，才能拦截全部导弹。

输入格式

一行或多行： $n$ 个正整数，表示导弹依次飞来的高度（高度 $\le 30000$ ， $1 \le n \le 1000$ ）

输出格式

一个整数 $k$ ，表示最少需要的系统套数

样例输入

389 207 155 300 299 170 158 65

样例输出

样例解释

导弹高度序列：389, 207, 155, 300, 299, 170, 158, 65。

系统 1 拦截：389 → 207 → 155（之后 300 比 155 高，不能用系统 1）
系统 2 拦截：300 → 299 → 170 → 158 → 65

最少需要 2 套系统。

贪心策略

对每一颗导弹，找一套能拦截它（当前高度 $\ge$ 导弹高度）且剩余高度最小的系统去拦截。如果找不到任何系统能拦截，就新增一套。

为什么对？

对于当前导弹高度 $h$ ，我们必须在所有能拦截它的系统中选一套。选"刚好能拦住它"（剩余高度最小但仍 $\ge h$ ）的系统，可以把剩余高度大的系统留给后面更高的导弹。这就是"能省则省、精准匹配"的思想。

💡 这个策略也叫最佳适配（Best Fit）：每次都选"浪费最少"的那个。

解题思路

维护数组 sys[]，sys[i] = 第 $i$ 套系统当前能拦截的最高高度（即该系统上次拦截的导弹高度）
遍历每颗导弹高度 $x$ $x$ ：
- 在现有系统中找"最小且 $\ge x$ "的系统
- 找到 → 更新该系统高度为 $x$
- 找不到 → 新增系统，高度为 $x$
最后的系统数量即为答案

C++ 代码

#include <iostream>
using namespace std;

int sys[1005];  // sys[i] = 第i套系统当前拦截高度
int k = 0;      // 当前系统数量

int main() {
    int n, x;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> x;
        // 找"最小且 >= x"的系统
        int best = -1;
        for (int j = 1; j <= k; j++) {
            if (sys[j] >= x) {
                if (best == -1 || sys[j] < sys[best]) {
                    best = j;
                }
            }
        }
        if (best != -1) {
            sys[best] = x;  // 用该系统拦截，高度更新为x
        } else {
            k++;
            sys[k] = x;     // 新增系统
        }
    }
    cout << k << endl;
    return 0;
}

代码说明

要点	说明
`sys[j] >= x`	系统 $j$ 能拦截当前导弹
`sys[j] < sys[best]`	在所有能拦截的系统中选高度最小的（最佳适配）
`sys[best] = x`	拦截后该系统高度降低到当前导弹高度
时间复杂度	以上为 $O(n^2)$ ，对于 $n \le 1000$ 足够；若优化可用 `upper_bound` 做到 $O(n \log n)$
等价问题	本题等价于求最少非递增子序列覆盖，也等价于求序列的最长上升子序列长度

例6.5 活动选择 —— "早点结束，多办几场"

题目描述

学校礼堂在同一时间只能被一个活动使用。现在有 $n$ 个活动需要申请使用礼堂，每个活动有起始时间 $begin_i$ 和结束时间 $end_i$ （ $begin_i < end_i$ ）。请你选择尽可能多的活动，使得它们互不冲突。

输入格式

第一行：整数 $n$ （ $n \le 1000$ ）
接下来 $n$ 行：每行两个整数 $begin_i$ 和 $end_i$ （ $0 < begin_i < end_i \le 32767$ ）

输出格式

一个整数：最多能安排的活动个数

样例输入

样例输出

样例解释

一种最优安排方案：选择 (1,4) → (5,7) → (8,11) → (12,14)，共 4 个活动。注意活动之间刚好衔接（前一个结束于 7，下一个开始于 8）是合法的。

贪心策略

按结束时间从小到大排序。每次选一个结束时间最早且不与已选活动冲突的活动。

为什么对？

在所有可选活动中，结束最早的那个给后面的活动留出了最多的剩余时间。因此优先选它，不会导致最终结果变差——这一结论可以通过"交换论证法"严格证明：

假设最优解没有选最早结束的活动 $A$ ，而是选了另一个活动 $B$ （ $B$ 结束得更晚）。把 $B$ 换成 $A$ ， $A$ 比 $B$ 更早结束，不会和最优解中后续的活动产生更多冲突。所以选最早结束的活动一定是最优的。

解题思路

将所有活动按 $end$ 升序排序
选第一个活动（它结束最早），记 lastEnd = a[1].end
依次检查后续活动：如果当前活动的 $begin \ge lastEnd$ ，就选它，更新 lastEnd
计数选中的活动数

C++ 代码

#include <iostream>
#include <algorithm>
using namespace std;

struct Activity {
    int begin, end;
} a[1005];

bool cmp(Activity x, Activity y) {
    return x.end < y.end;  // 按结束时间升序排序
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].begin >> a[i].end;
    }
    sort(a + 1, a + n + 1, cmp);

    int ans = 1;                // 第一个活动必选（它结束最早）
    int lastEnd = a[1].end;     // 上一个选中活动的结束时间
    for (int i = 2; i <= n; i++) {
        if (a[i].begin >= lastEnd) {  // 不冲突
            ans++;
            lastEnd = a[i].end;
        }
    }
    cout << ans << endl;
    return 0;
}

代码说明

要点	说明
`cmp` 按 `end` 排序	这是整个算法的灵魂——不能按开始时间排序！
`a[i].begin >= lastEnd`	注意是 $\ge$ ，刚好结束就可以开始下一个
第一个活动必选	按 end 排序后，第一个活动结束最早，选它最优
时间复杂度	排序 $O(n \log n)$ ，贪心选择 $O(n)$

例6.6 整数区间 —— "选最右的点，覆盖最多的区间"

题目描述

给出 $n$ 个闭区间 $[a, b]$ 。请找出一个含元素个数最少的整数集合，使得对于每一个区间，都至少有一个整数属于该集合。输出该集合的元素个数。

输入格式

第一行：整数 $n$ （ $1 \le n \le 10000$ ）
接下来 $n$ 行：每行两个整数 $a, b$ （ $0 \le a \le b \le 10000$ ），表示一个闭区间

输出格式

一行：集合中最少的整数个数

样例输入

样例输出

样例解释

4 个区间分别为 [3,6], [2,4], [0,2], [4,7]。最优方案选两个整数：2 和 6（或 2 和 4、2 和 5 等），可以覆盖所有区间。

贪心策略

按区间右端点从小到大排序。依次检查每个区间：如果当前选的点集还不能覆盖它，就把这个区间的右端点加入集合。

为什么对？

对于当前区间 $[a, b]$ ，如果要选一个点覆盖它，选右端点 $b$ 是最"贪"的—— $b$ 最靠右，能够同时覆盖后面尽可能多的区间（因为后面的区间右端点更靠右，左端点很可能 $\le b$ ）。这和例6.5"活动选择"形成有趣的对比：

	活动选择（6.5）	整数区间（6.6）
目的	选最多的不重叠区间	选最少的点覆盖所有区间
排序	按结束时间升序	按右端点升序
选择	选开始最早的	选右端点

💡 这两个问题互为"对偶"——理解了其中一个，另一个就自然懂了。

解题思路

将所有区间按 $b$ （右端点）升序排序
维护 lastPoint = 上一个选中的整数（初始为 -1）
遍历每个区间：
- 如果 $lastPoint$ 已经在当前区间内（ $a \le lastPoint \le b$ ），跳过
- 否则，选当前区间的右端点 $b$ ，答案 +1，更新 lastPoint = b

C++ 代码

#include <iostream>
#include <algorithm>
using namespace std;

struct Interval {
    int a, b;
} itv[10005];

bool cmp(Interval x, Interval y) {
    return x.b < y.b;  // 按右端点升序排序
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> itv[i].a >> itv[i].b;
    }
    sort(itv + 1, itv + n + 1, cmp);

    int ans = 0;
    int lastPoint = -1;  // 上一次选择的点（-1保证第一个区间不会被跳过）
    for (int i = 1; i <= n; i++) {
        // 如果上一个点已经覆盖了当前区间，无需再选
        if (lastPoint >= itv[i].a && lastPoint <= itv[i].b) {
            continue;
        }
        // 否则选当前区间的右端点（最"贪"的选择）
        ans++;
        lastPoint = itv[i].b;
    }
    cout << ans << endl;
    return 0;
}

代码说明

要点	说明
`cmp` 按 `b` 排序	右端点越小的区间越先处理
`lastPoint >= a && lastPoint <= b`	判断上次选的点是否已覆盖当前区间
`lastPoint = -1`	初始设为 -1，保证第一个区间不会被漏掉（因为 $a \ge 0$ ）
贪心选择 `b`	每发现一个未覆盖区间，直接选它的最右端点

三、总结

六题对比一览

例题	题目	核心贪心策略	排序依据	复杂度
6.1	排队接水	短的先来	接水时间升序	$O(n \log n)$
6.2	均分纸牌（NOIP2002）	差多少给多少	无需排序，从左到右递推	$O(n)$
6.3	删数问题（NOIP1994）	删第一个山峰	单调栈，无需排序	$O(n)$
6.4	拦截导弹（NOIP1999）	最佳适配	贪心匹配，无需排序	$O(n^2)$ / $O(n \log n)$
6.5	活动选择	选最早结束的	结束时间升序	$O(n \log n)$
6.6	整数区间	选最右端点	右端点升序	$O(n \log n)$

贪心问题的识别特征

当你遇到这些问题，优先考虑贪心：

要求最小 / 最大（最小次数、最多活动、最大收益……）
可以排序后依次处理（排序往往是贪心第一步）
涉及区间调度（活动选择、区间覆盖、区间选点）
每一步有明确的最优选择（当前最优解唯一确定）

贪心三步法

步骤一：设计策略 → 每一步按什么规则选？
步骤二：举例验证 → 拿几个例子手动模拟，看是否符合预期
步骤三：尝试证明 → 交换论证、递推归纳、反证法……

💡 记住：贪心算法不是"猜"，每一步都是可证明的局部最优。6 道题反复咀嚼，贪心的感觉就来了。加油！

贪心算法入门：用"眼前的智慧"解决问题

一、什么是贪心算法？

两个关键问题

常见套路

二、例题精讲

例6.1 排队接水 —— "快的先来"

例6.2 均分纸牌（NOIP2002）—— "多了给隔壁，少了问隔壁要"

例6.3 删数问题（NOIP1994）—— "删掉第一个山峰"

例6.4 拦截导弹问题（NOIP1999）—— "用最少的系统接住所有导弹"

例6.5 活动选择 —— "早点结束，多办几场"

例6.6 整数区间 —— "选最右的点，覆盖最多的区间"

三、总结

六题对比一览

贪心问题的识别特征

贪心三步法

状态

开发

支持

还没有账户？

登录