第8章贪心算法

🎯 本章学习目标

通过本章的学习，你将能够：

理解贪心思想：掌握贪心算法的核心——每步选局部最优，期望得到全局最优
掌握两个基本要素：理解贪心选择性质和最优子结构
区分贪心与DP：清楚贪心和动态规划的区别与适用场景
掌握活动选择：理解按结束时间排序的贪心策略
掌握区间问题：能解决区间覆盖、区间选点等经典区间贪心问题
掌握合并问题：能用小根堆解决合并果子类问题
掌握排队问题：理解短作业优先的贪心策略
理解乘船问题：掌握双指针法解决最优搭配问题
使用优先队列：能用 priority_queue 实现动态取最值的贪心
证明贪心正确性：了解交换论证和反证法，能判断策略是否正确

🗺️ 本章知识图谱

贪心算法
├── 基础概念
│   ├── 核心思想：每步选局部最优 → 全局最优
│   ├── 两个基本要素
│   │   ├── 贪心选择性质
│   │   └── 最优子结构
│   ├── 贪心 vs 动态规划
│   │   ├── 贪心：勇往直前不回头
│   │   └── DP：三思而后行
│   └── 正确性证明
│       ├── 交换论证
│       └── 反证法
├── 经典模型
│   ├── 区间调度类
│   │   ├── 活动选择（按结束时间排序）
│   │   ├── 区间覆盖（按左端点排序，选最远右端点）
│   │   └── 区间选点（按右端点排序）
│   ├── 合并类
│   │   ├── 合并果子（哈夫曼思想）
│   │   └── 小根堆（priority_queue）
│   ├── 排序类
│   │   ├── 排队接水（短的在前）
│   │   └── 找零问题（规范货币）
│   └── 搭配类
│       ├── 乘船问题（最轻+最重双指针）
│       └── 渡桥问题
├── 常用工具
│   ├── 排序（sort）
│   ├── 优先队列（priority_queue）
│   └── 双指针
└── 常见反例
    ├── 01背包（贪心不适用）
    └── 最长上升子序列（要用DP）

一、引言：什么是贪心算法？

贪心算法（Greedy Algorithm）的核心思想可以用一句话概括：

每一步都做出当前看起来最好的选择，希望通过局部最优推导出全局最优。

就像去自助餐厅吃饭——每次只拿眼前最想吃的那道菜，希望最终拼出一顿最满意的大餐。当然，这种策略不一定总能成功（比如可能全是凉菜没热菜），这就引出了贪心法最关键的问题：什么时候贪心是对的？

贪心算法在 GESP 五级中出现频率极高，几乎每套试卷都会涉及。与动态规划相比，贪心代码通常更短、思路更直接，但证明正确性往往更难——这也是考试的重点和难点。

二、贪心算法核心概念

2.1 贪心算法的两个基本要素

一个问题能够使用贪心算法求得最优解，必须同时满足以下两个性质：

性质	含义	通俗理解
贪心选择性质	每一步的局部最优选择，可以导致全局最优解	"走一步看一步，每步选最好"是可行的
最优子结构	问题的最优解包含其子问题的最优解	"大问题的好答案，由小问题的好答案组成"

⚠️ 关键区分：最优子结构也是动态规划的必要条件。贪心与 DP 的核心区别在于贪心选择性质——贪心要求"每步选当前最优即可"，而 DP 需要"考虑所有子问题的解再做选择"。

2.2 贪心 vs 动态规划

维度	贪心算法	动态规划
决策方式	每步只选当前最优，不回头	枚举所有选择，取最优
子问题关系	每次贪心选择后只剩下一个子问题	选择后可能产生多个子问题
时间复杂度	通常较低（排序后 O(n) 遍历）	通常较高（O(n²)、O(nW) 等）
正确性证明	需要额外证明贪心策略的正确性	状态转移方程本身即保证正确
适用场景	问题具有贪心选择性质	问题具有最优子结构 + 重叠子问题
典型例子	活动选择、合并果子	背包问题、最长公共子序列

一句话记忆：贪心是"勇往直前不回头"，DP 是"三思而后行"。

2.3 贪心策略的正确性证明

考试中经常要求判断某个贪心策略是否正确。以下是两种最常用的证明方法：

方法一：交换论证（Exchange Argument）

核心思路：假设存在一个最优解与贪心解不同，通过交换其中的某些元素，证明交换后不会变差，从而说明贪心解不劣于任何最优解。

经典例子——活动选择问题：

贪心策略：每次选结束时间最早的活动
证明：设贪心选的第一个活动为 A（结束最早），最优解选的第一个活动为 B。由于 A 结束 ≤ B 结束，将 B 替换为 A 后，剩余可用时间不会减少，因此最优解不会变差。

方法二：反证法

核心思路：假设贪心策略得到的解不是最优解，推导出矛盾。

使用模板：

假设贪心解 G 不是最优解，存在最优解 O 比 G 更好。
在 G 与 O 的第一个不同选择处，分析：
  贪心选了 g，最优解选了 o（o ≠ g）。
  由贪心策略，g 是当前最优选择，因此 ...（推出矛盾）。
故假设不成立，贪心解就是最优解。

📌 考试提示：GESP 五级的选择题常给出几个贪心策略让你判断哪个正确。不需要写出严格证明，但要能通过小例子验证或凭直觉判断。

三、经典贪心题型逐个精讲

3.1 区间调度（活动选择问题）

📋 题意

有 n 个活动，每个活动有开始时间 s[i] 和结束时间 f[i]。同一时间只能参加一个活动，活动时间不能重叠。问最多能参加多少个活动？

💡 贪心策略

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

为什么按结束时间排序？——结束越早，留给后续活动的时间越多。

✅ 正确性说明（交换论证）

设贪心选择的第一个活动为 A（结束时间最早），最优解选择的第一个活动为 B。

f[A] ≤ f[B]（A 是结束最早的）
用 A 替换 B，A 的结束时间更早，不会与后续活动产生更多冲突
因此替换后的解仍然是最优解，说明贪心选择是安全的

💻 C++ 代码

cpp

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

// 活动结构体
struct Activity {
    int start;
    int finish;
};

// 按结束时间从小到大排序
bool cmp(const Activity& a, const Activity& b) {
    return a.finish < b.finish;
}

int main() {
    int n;
    cin >> n;
    vector<Activity> acts(n);
    for (int i = 0; i < n; i++) {
        cin >> acts[i].start >> acts[i].finish;
    }

    // 按结束时间排序
    sort(acts.begin(), acts.end(), cmp);

    int count = 0;
    int lastFinish = -1;  // 上一个选中活动的结束时间

    for (int i = 0; i < n; i++) {
        // 如果当前活动的开始时间 >= 上一个活动的结束时间，则可以选
        if (acts[i].start >= lastFinish) {
            count++;
            lastFinish = acts[i].finish;
        }
    }

    cout << count << endl;
    return 0;
}

输入样例：

输出：3（选择 1-3、4-7、7-10）

⚠️ 易错点：
排序依据是结束时间，不是开始时间，也不是活动时长！按开始时间排序或按时长排序都是错误的。
注意边界：如果允许一个活动的结束时间等于另一个的开始时间（端点可重合），判断条件用 >=；如果不允许，用 >。

3.2 区间覆盖（线段覆盖问题）

📋 题意

给定一个目标区间 [start, end] 和 n 个小区间 [l[i], r[i]]，选择最少的小区间，使得它们的并集完全覆盖目标区间。

💡 贪心策略

将所有小区间按左端点从小到大排序
从目标区间起点开始，在所有左端点 ≤ 当前已覆盖位置的区间中，选择右端点最大的那个
更新当前已覆盖位置为该右端点，重复直到覆盖整个目标区间

✅ 正确性说明

在已覆盖位置左侧的区间无法扩展覆盖范围；在所有能接上的区间中，右端点越大覆盖得越远，留给后续的"缺口"越小，因此每步选右端点最大的区间不会更差。

💻 C++ 代码

cpp

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

struct Interval {
    int l, r;
};

bool cmp(const Interval& a, const Interval& b) {
    return a.l < b.l;  // 按左端点排序
}

int main() {
    int n, targetL, targetR;
    cin >> n >> targetL >> targetR;

    vector<Interval> segs(n);
    for (int i = 0; i < n; i++) {
        cin >> segs[i].l >> segs[i].r;
    }
    sort(segs.begin(), segs.end(), cmp);

    int cur = targetL;   // 当前已覆盖到的位置
    int i = 0;
    int count = 0;

    while (cur < targetR) {
        int bestR = cur;  // 本轮能扩展到的最远右端点

        // 在所有左端点 <= cur 的区间中，找右端点最大的
        while (i < n && segs[i].l <= cur) {
            bestR = max(bestR, segs[i].r);
            i++;
        }

        if (bestR == cur) {
            // 无法继续覆盖，说明无解
            cout << -1 << endl;
            return 0;
        }

        cur = bestR;
        count++;
    }

    cout << count << endl;
    return 0;
}

⚠️ 易错点：与活动选择不同，这里排序依据是左端点（从小到大），选择时看右端点（最大的）。不要和活动选择的排序方式搞混！

3.3 找零问题（硬币问题）

📋 题意

有若干种面值的硬币，每种硬币数量无限。找零金额为 m，最少需要多少枚硬币？

💡 贪心策略

每次优先使用面值最大的硬币。

但要注意：贪心策略并非对所有硬币系统都正确！

硬币系统	贪心是否正确	说明
1, 5, 10, 50, 100, 500（人民币/日元）	✅	标准倍数关系，贪心正确
1, 5, 10, 25（美元）	✅	贪心正确
1, 3, 4	❌	找零 6：贪心得 4+1+1=3枚，最优 3+3=2枚
1, 7, 10	❌	找零 14：贪心得 10+1+1+1+1=5枚，最优 7+7=2枚

✅ 贪心适用条件

当硬币面值满足规范货币系统（canonical coin system）的条件时，贪心算法正确。五级考试中，如果题目给出的硬币面值是常见的货币体系（如人民币、美元），可以直接用贪心。如果面值是"特殊"的，则需要用 DP。

💻 C++ 代码（贪心版，适用于规范货币系统）

cpp

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

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> coins(n);
    for (int i = 0; i < n; i++) {
        cin >> coins[i];
    }

    // 从大到小排序
    sort(coins.begin(), coins.end(), greater<int>());

    int count = 0;
    for (int i = 0; i < n; i++) {
        count += m / coins[i];   // 能用多少大面值就用多少
        m %= coins[i];           // 剩余金额
    }

    cout << count << endl;
    return 0;
}

⚠️ 高频考点：考试常出反例！题目给出非规范硬币系统（如面值 1、3、4），要求判断贪心是否正确，或者要求用 DP 求解。不要见到硬币题就贪心。

3.4 合并果子（哈夫曼型贪心）

📋 题意（NOIP 经典题）

果园里有 n 堆果子，每堆果子有一定重量。每次可以合并两堆果子，消耗的体力等于两堆果子的重量之和。求把所有果子合并成一堆所需的最小体力。

💡 贪心策略

每次合并当前重量最小的两堆果子。

这本质上就是哈夫曼树的构造过程——使所有叶子节点的带权路径长度之和最小。

✅ 正确性说明

最小的两堆果子被合并的次数最多（在树的最深层），因此让它们最小可以使总代价最小
每次合并后，新堆重新参与下一轮选择，这正是哈夫曼树的构造规则
可以用交换论证：如果最优解中某次合并的不是最小的两堆，交换后总代价不会增加

💻 C++ 代码（优先队列实现）

cpp

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

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

    // 小根堆：每次取出最小的两个元素
    priority_queue<long long, vector<long long>, greater<long long>> pq;

    for (int i = 0; i < n; i++) {
        long long x;
        cin >> x;
        pq.push(x);
    }

    long long totalCost = 0;

    while (pq.size() > 1) {
        // 取出最小的两堆
        long long a = pq.top(); pq.pop();
        long long b = pq.top(); pq.pop();

        long long merged = a + b;
        totalCost += merged;
        pq.push(merged);  // 合并后的新堆放回队列
    }

    cout << totalCost << endl;
    return 0;
}

输入样例：

3
1 2 9

输出：15（先合并 1+2=3，再合并 3+9=12，总代价 3+12=15）

⚠️ 易错点：
合并后的新堆要放回队列参与后续合并！不要忘记 pq.push(merged)。
数据范围：果子重量可能较大，累加和可能超过 int 范围，使用 long long 保险。
使用的是小根堆（greater<long long>），不要写成默认的大根堆。

3.5 排队接水

📋 题意

有 n 个人排队接水，第 i 个人的接水时间为 t[i]。只有一个水龙头，所有人都要接完水。如何安排顺序，使得所有人的等待时间总和最小？

💡 贪心策略

接水时间短的人排在前面。（按接水时间从小到大排序）

✅ 正确性说明

假设相邻两人 A、B 的接水时间分别为 a、b，且 a > b。

顺序 A→B：A 等待 0，B 等待 a，总等待 = 0 + a = a
顺序 B→A：B 等待 0，A 等待 b，总等待 = 0 + b = b
因为 a > b，所以 a > b，时间短的排前面更优（总等待越小越好）
这就是交换论证：任何逆序对交换后都不会变差

💻 C++ 代码

cpp

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

int main() {
    int n;
    cin >> n;
    vector<int> t(n);
    for (int i = 0; i < n; i++) {
        cin >> t[i];
    }

    // 按接水时间从小到大排序
    sort(t.begin(), t.end());

    long long totalWait = 0;  // 所有人等待时间总和
    long long currentWait = 0; // 当前累计等待时间

    for (int i = 0; i < n; i++) {
        totalWait += currentWait;      // 第 i 个人的等待时间
        currentWait += t[i];           // 累加接水时间
    }

    cout << totalWait << endl;
    return 0;
}

输入样例：

5
3 1 4 2 5

排序后：1, 2, 3, 4, 5 等待时间：0 + 1 + 3 + 6 + 10 = 20 输出：20

⚠️ 易错点：注意题目问的是"等待时间总和"还是"总耗时（最后一个人接完水的时间）"。总耗时无论怎么排都一样（等于所有人接水时间之和），只有等待时间总和受顺序影响。

3.6 渡桥问题（乘船问题）

📋 题意

有 n 个人要过河，只有一艘船，船最多载 2 人。船需要有人划回来。每个人的过河时间不同，两人同乘时按较慢者的时间计算。求全部过河的最短时间。

💡 贪心策略

经典的"四人过河"模型。每次送最慢的两个人过河，有两种策略，取较优者：

设最快的两人为 a、b（a ≤ b），最慢的两人为 c、d（c ≤ d）：

策略一（最快的来回送）：a 和 d 过去 → a 回来 → a 和 c 过去 → a 回来耗时：d + a + c + a = d + c + 2a
策略二（最快的两人协作）：a 和 b 过去 → a 回来 → c 和 d 过去 → b 回来耗时：b + a + d + b = d + a + 2b

每次取两种策略的较小值，直到所有人过河。

💻 C++ 代码

cpp

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

int main() {
    int n;
    cin >> n;
    vector<int> t(n);
    for (int i = 0; i < n; i++) {
        cin >> t[i];
    }
    sort(t.begin(), t.end());  // 从小到大排序

    int i = n - 1;  // 从最慢的人开始
    int total = 0;

    while (i > 2) {
        // 策略一：最快的a分别送c和d
        int option1 = t[i] + t[0] + t[i-1] + t[0];
        // 策略二：a和b先过，a回，c和d过，b回
        int option2 = t[1] + t[0] + t[i] + t[1];
        total += min(option1, option2);
        i -= 2;  // 最慢的两人已过河
    }

    // 处理剩余 1~3 人的边界情况
    if (i == 2) {
        // 剩3人：a和c过，a回，a和b过
        total += t[2] + t[0] + t[1];
    } else if (i == 1) {
        // 剩2人：一起过
        total += t[1];
    } else {
        // 剩1人
        total += t[0];
    }

    cout << total << endl;
    return 0;
}

输入样例：

4
1 2 5 10

策略一：10+1+5+1 = 17
策略二：2+1+10+2 = 15 → 选策略二
剩余2人：1+2=2，总时间 15+2=17

输出：17

⚠️ 易错点：
渡桥问题是贪心算法中策略最复杂的一种，需要同时比较两种方案，不能只选一种。
注意边界处理：最后剩下 1 人、2 人、3 人的情况各不相同。
五级考试中如果出现，通常会简化为"乘船问题"——每船限乘 2 人，求最少船数（这其实是更简单的"最大搭配贪心"）。

🌊 简化版：乘船问题（最大搭配）

题意：n 个人，每个人体重 w[i]，每船最大载重 C，每船最多 2 人。求最少需要多少条船。

贪心策略：最重的人和最轻的人搭配——如果两人能同乘，则同乘；否则最重的人单独一船。

cpp

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

int main() {
    int n, C;
    cin >> n >> C;
    vector<int> w(n);
    for (int i = 0; i < n; i++) cin >> w[i];
    sort(w.begin(), w.end());

    int left = 0, right = n - 1;
    int boats = 0;

    while (left <= right) {
        if (left == right) {
            // 只剩一人
            boats++;
            break;
        }
        if (w[left] + w[right] <= C) {
            // 最轻和最重可以同乘
            left++;
            right--;
        } else {
            // 最重的人单独一船
            right--;
        }
        boats++;
    }

    cout << boats << endl;
    return 0;
}

四、优先队列（priority_queue）在贪心中的使用

📚 拓展 · 超纲：priority_queue 属 STL 容器，五级考纲未单列。但它是实现哈夫曼型贪心最顺手的工具，建议了解基本用法；若考到，通常也会给出替代写法。

很多贪心问题需要反复"取最大值/最小值"，优先队列是最高效的工具。

4.1 priority_queue 基础用法

cpp

#include <queue>
#include <vector>
#include <functional>
using namespace std;

// 大根堆（默认）：每次取最大的元素
priority_queue<int> maxHeap;

// 小根堆：每次取最小的元素（合并果子用这个）
priority_queue<int, vector<int>, greater<int>> minHeap;

// 基本操作
maxHeap.push(3);    // 入队
maxHeap.push(1);
maxHeap.push(5);
cout << maxHeap.top();  // 5（查看堆顶，不弹出）
maxHeap.pop();          // 弹出堆顶（5）
cout << maxHeap.size(); // 2
cout << maxHeap.empty();// 0（非空）

4.2 自定义比较函数

cpp

// 按某个字段排序的结构体
struct Node {
    int id;
    int value;
};

// 大根堆：按 value 从大到小
struct CmpMax {
    bool operator()(const Node& a, const Node& b) {
        return a.value < b.value;  // 注意：大根堆用 <
    }
};

priority_queue<Node, vector<Node>, CmpMax> pq;

📌 记忆技巧：priority_queue 的比较函数和 sort 相反——greater<T> 对应小根堆，less<T>（默认）对应大根堆。

4.3 优先队列适用的贪心场景

场景	堆类型	典型问题
每次取最小的两个合并	小根堆	合并果子、哈夫曼编码
每次取最大的元素	大根堆	最后一块石头的重量
动态维护前 K 大/小	小根堆/大根堆	Top-K 问题
每次取代价最小的边	小根堆	Kruskal 最小生成树（七级内容）

五、贪心不适用的反例

贪心虽然优雅，但并非万能。以下是几个经典的"贪心失败"案例：

5.1 0/1 背包问题

问题：背包容量 50，物品：

物品 A：重量 10，价值 60（单位价值 6）
物品 B：重量 20，价值 100（单位价值 5）
物品 C：重量 30，价值 120（单位价值 4）

贪心策略（按单位价值排序）：选 A（60）+ B（100）= 160，剩余 20 容量无法装 C 最优解：选 B（100）+ C（120）= 220 ✅

贪心失败的原因：0/1 背包中物品不可分割，局部最优可能导致背包空间浪费。

💡 对比：如果物品可以分割（分数背包），按单位价值排序的贪心策略就是正确的。这是贪心与 DP 的经典分界线。

5.2 硬币问题（非规范货币系统）

前面已经提到：面值 1、3、4，找零 6：

贪心：4 + 1 + 1 = 3 枚
最优：3 + 3 = 2 枚

5.3 判断贪心是否适用的经验法则

信号	贪心可能适用 ✅	贪心可能不适用 ❌
问题特征	排序后依次选择即可	选与不选会影响后续多种可能
子问题数量	每次选择后只剩一个子问题	选择后产生多个需要比较的子问题
经典模型	活动选择、哈夫曼、排队	0/1 背包、最长路径
验证方法	能通过交换论证证明	能找到反例使贪心失败

⚠️ 考试策略：如果题目看起来像贪心但你不确定正确性，试试 DP！GESP 五级中数据范围通常允许 DP 通过。

六、贪心解题一般步骤

┌─────────────────────────────────────────────┐
│  第一步：识别贪心适用性                         │
│  → 问题是否具有贪心选择性质？                    │
│  → 能否通过排序后依次选择来解决？                 │
│  → 尝试找反例：如果能找到反例，改用 DP           │
├─────────────────────────────────────────────┤
│  第二步：设计排序/选择策略                      │
│  → 按什么排序？（结束时间？左端点？大小？）       │
│  → 每次选什么？（最早结束？最小？最大搭配？）     │
├─────────────────────────────────────────────┤
│  第三步：证明正确性（至少在脑中验证）             │
│  → 交换论证：能否交换后不变差？                  │
│  → 反证法：假设不是最优，能否推出矛盾？           │
│  → 小例子手算验证                               │
├─────────────────────────────────────────────┤
│  第四步：编码实现                              │
│  → 排序 + 遍历选择（O(n log n)）               │
│  → 或优先队列动态选择（O(n log n)）            │
│  → 注意数据范围，必要时用 long long             │
└─────────────────────────────────────────────┘

七、📝 实战练习

练习题 1（单选题）

题目： 关于活动选择问题，以下贪心策略正确的是（）

A. 按活动开始时间从小到大排序，依次选择不冲突的活动
B. 按活动持续时间从小到大排序，依次选择不冲突的活动
C. 按活动结束时间从小到大排序，依次选择不冲突的活动
D. 按活动重要程度从大到小排序，依次选择不冲突的活动

🔑 点击查看答案与解析

答案： C

解析：

A 错误：开始早不代表结束早，可能选了一个开始早但持续超长的活动，挤占大量时间
B 错误：持续时间短不代表结束早，存在反例
C 正确 ✅：按结束时间排序是活动选择问题的经典贪心策略，可用交换论证证明正确性
D 错误：题目中没有"重要程度"的信息

💡 记住结论：活动选择按结束时间排序，这是最经典的贪心题。

练习题 2（判断题）

题目： 只要问题具有最优子结构，就一定可以用贪心算法求解。（）

🔑 点击查看答案与解析

答案： 错误 ❌

解析： 贪心算法需要同时满足两个条件：

贪心选择性质：每步的局部最优选择可以导致全局最优
最优子结构：大问题的最优解包含子问题的最优解

只有最优子结构是不够的——动态规划也需要最优子结构。贪心比 DP 多了一个"贪心选择性质"的要求。

🍎 生活比喻：最优子结构就像"搭积木"——大积木由小积木组成。贪心选择性质就像"每次随便放一块都能刚好放对位置"——不是所有积木都能这样搭的。

练习题 3（单选题）

题目： 有 4 堆果子，重量分别为 1, 2, 3, 4。每次合并两堆，消耗的体力等于两堆重量之和。把所有果子合并成一堆，最少消耗多少体力？（）

A. 10
B. 19
C. 20
D. 24

🔑 点击查看答案与解析

答案： B

解析：

这是经典的"合并果子"问题，贪心策略是每次合并最小的两堆（哈夫曼树思想）。

过程：

合并 1 + 2 = 3，消耗 3，剩余 [3, 3, 4]
合并 3 + 3 = 6，消耗 6，剩余 [4, 6]
合并 4 + 6 = 10，消耗 10，剩余 [10]

总消耗 = 3 + 6 + 10 = 19

选 B。

🔥 为什么每次选最小的？因为小的果子会被多次合并（每次上面加新的都要带着它），所以小的合并次数多、大的合并次数少，总消耗最小。

练习题 4（单选题）

题目： 有 3 个人接水，接水时间分别为 2 分钟、5 分钟、3 分钟。要使所有人的等待时间总和最少，应该按什么顺序接水？（）

A. 2, 5, 3
B. 5, 3, 2
C. 2, 3, 5
D. 3, 2, 5

🔑 点击查看答案与解析

答案： C

解析：

排队接水的贪心策略：接水时间短的排在前面。

按本章代码口径，第 i 个人的等待时间 = 排在他前面所有人接水时间之和：

验证 C 选项（2, 3, 5）：

第 1 人等待 0 分钟
第 2 人等待 2 分钟
第 3 人等待 2 + 3 = 5 分钟
总等待时间 = 0 + 2 + 5 = 7

对比 B 选项（5, 3, 2）：

总等待 = 0 + 5 + (5 + 3) = 13

7 < 13，所以短的在前等待时间最少，选 C。

💡 原理：排在前面的人，他的接水时间会被后面所有人"分摊"。所以时间短的放前面，让更多人分摊短的时间，总等待时间最少。

练习题 5（判断题）

题目： 用贪心算法（每次选最大面值）找零，对于任何货币系统都能得到最少硬币数。（）

🔑 点击查看答案与解析

答案： 错误 ❌

解析： 贪心找零只对规范货币系统（如人民币 1/2/5/10/20/50/100）有效。

反例：如果面值是 1, 3, 4，要找 6 元：

贪心：4 + 1 + 1 = 3 枚
最优：3 + 3 = 2 枚

所以贪心不总是对的！

🍎 生活比喻：人民币的面值设计是"规范"的，所以贪心找零没问题。但如果有人乱设计面值（比如有 4 元的硬币），贪心就会翻车。

练习题 6（单选题）

题目： 在数轴上有 n 个区间，要求选最少的点，使得每个区间至少包含一个点。正确的贪心策略是？（）

A. 按区间左端点排序，每次选最左边的点
B. 按区间右端点排序，每次选右端点
C. 按区间长度排序，每次选最短区间的中点
D. 按区间左端点排序，每次选最右边的点

🔑 点击查看答案与解析

答案： B

解析：

区间选点问题（也叫"射气球"问题）的正确贪心策略：

按右端点从小到大排序
每次选第一个区间的右端点作为"点"
去掉所有包含这个点的区间
重复直到所有区间都被覆盖

为什么选右端点？因为右端点越靠左，越有可能"射穿"更多后面的区间（后面的区间左端点更大）。

选 B。

💡 经典口诀：区间选点按右端，第一个右端就是点；去掉包含这个点的，剩下的继续同样干。

练习题 7（单选题）

题目： 关于贪心算法和动态规划，以下说法正确的是？（）

A. 贪心算法的时间复杂度一定比动态规划低
B. 能用贪心解决的问题，也一定能用动态规划解决
C. 贪心和动态规划都需要最优子结构
D. 贪心和动态规划的区别是贪心用递归，DP 用循环

🔑 点击查看答案与解析

答案： C

解析：

A 错误："一定"太绝对，要看具体问题
B 错误：有些问题贪心能做但 DP 不一定适用（或者说 DP 能做但贪心更高效）
C 正确 ✅：最优子结构是两者的共同要求。区别在于贪心还需要"贪心选择性质"
D 错误：贪心和 DP 都可以用递归或迭代实现，核心区别是决策方式

💡 一句话总结：贪心 = 勇往直前不回头；DP = 三思而后行。贪心赌的是"每步最优 = 全局最优"，DP 是老老实实枚举所有可能。

练习题 8（编程题）

题目： 活动选择问题：有 n 个活动，每个活动有开始时间 s[i] 和结束时间 e[i]。选择最多的不冲突活动，输出最多能选几个活动。

输入：第一行 n，接下来 n 行每行两个整数 s[i] 和 e[i]
输出：最多能选的活动数

样例输入：

样例输出：

（选活动 1-3 和 4-6，共 2 个）

🔑 点击查看答案与解析

参考答案：

cpp

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

struct Activity {
    int start, end;
};

bool compare(const Activity& a, const Activity& b) {
    return a.end < b.end;  // 按结束时间升序
}

int main() {
    int n;
    cin >> n;
    vector<Activity> acts(n);
    for (int i = 0; i < n; i++) {
        cin >> acts[i].start >> acts[i].end;
    }
    
    sort(acts.begin(), acts.end(), compare);  // 按结束时间排序
    
    int count = 0;
    int lastEnd = -1;  // 上一个选中活动的结束时间
    for (int i = 0; i < n; i++) {
        if (acts[i].start >= lastEnd) {  // 不冲突
            count++;
            lastEnd = acts[i].end;
        }
    }
    
    cout << count << endl;
    return 0;
}

解析：

活动选择的经典贪心解法：

按结束时间从小到大排序
遍历每个活动，如果和上一个选中的活动不冲突（开始时间 ≥ 上一个结束时间），就选它
每选一个，更新"上一个结束时间"

时间复杂度：排序 O(n log n) + 遍历 O(n) = O(n log n)

💡 为什么按结束时间排序是对的？可以用交换论证证明：假设最优解的第一个活动不是结束最早的，把它换成结束最早的活动，解不会变差。

八、📊 考点总结表

考点	重要程度	出题形式	易错点
贪心两个基本要素	⭐⭐⭐⭐⭐	选择/判断	贪心选择性质和最优子结构缺一不可
贪心 vs 动态规划	⭐⭐⭐⭐	选择/判断	核心区别：贪心不回头，DP考虑所有选择
活动选择（按结束时间排序）	⭐⭐⭐⭐⭐	编程题/选择	排序方式搞反
区间选点/射气球	⭐⭐⭐⭐	编程题/选择	按右端点排序，选右端点
合并果子（哈夫曼）	⭐⭐⭐⭐⭐	编程题/选择	用小根堆；每次取最小的两个
排队接水（短作业优先）	⭐⭐⭐⭐	选择/编程	按时间升序，短的在前
找零问题	⭐⭐⭐	选择/判断	只有规范货币系统贪心才对
乘船问题（双指针）	⭐⭐⭐	选择/编程	最轻+最重搭配
优先队列的使用	⭐⭐⭐⭐	代码填空	小根堆写法：`greater<int>`
贪心正确性判断	⭐⭐⭐⭐	选择/判断	找反例是检验贪心的好方法

⭐ 必背速记卡

┌─────────────────────────────────────────────┐
│         贪心算法 · 必背速记卡               │
├─────────────────────────────────────────────┤
│  1. 贪心核心：每步选局部最优 → 全局最优     │
│  2. 贪心两要素：贪心选择性质 + 最优子结构   │
│  3. 最优子结构是贪心和DP的共同要求         │
│  4. 贪心：勇往直前不回头；DP：三思而后行    │
│  5. 活动选择：按结束时间排序，选不冲突的    │
│  6. 区间选点：按右端点排序，选右端点       │
│  7. 合并果子：每次取最小两堆，用小根堆      │
│  8. 排队接水：短的在前，总等待最少         │
│  9. 找零贪心：只对规范货币系统有效         │
│ 10. 乘船问题：最轻最重配，双指针两头走      │
│ 11. 贪心利器：sort排序 + priority_queue    │
│ 12. priority_queue 默认是大根堆            │
│ 13. 小根堆写法：priority_queue<int, vector<int>, greater<int>>│
│ 14. 贪心要证明，交换论证和反证法           │
│ 15. 贪心拿不准？试试动态规划               │
└─────────────────────────────────────────────┘

第8章 贪心算法 ​

🎯 本章学习目标 ​

🗺️ 本章知识图谱 ​

一、引言：什么是贪心算法？ ​

二、贪心算法核心概念 ​

2.1 贪心算法的两个基本要素 ​

2.2 贪心 vs 动态规划 ​

2.3 贪心策略的正确性证明 ​

方法一：交换论证（Exchange Argument） ​

方法二：反证法 ​

三、经典贪心题型逐个精讲 ​

3.1 区间调度（活动选择问题） ​

📋 题意 ​

💡 贪心策略 ​

✅ 正确性说明（交换论证） ​

💻 C++ 代码 ​

3.2 区间覆盖（线段覆盖问题） ​

📋 题意 ​

💡 贪心策略 ​

✅ 正确性说明 ​

💻 C++ 代码 ​

3.3 找零问题（硬币问题） ​

📋 题意 ​

💡 贪心策略 ​

✅ 贪心适用条件 ​

💻 C++ 代码（贪心版，适用于规范货币系统） ​

3.4 合并果子（哈夫曼型贪心） ​

📋 题意（NOIP 经典题） ​

💡 贪心策略 ​

✅ 正确性说明 ​

💻 C++ 代码（优先队列实现） ​

3.5 排队接水 ​

📋 题意 ​

💡 贪心策略 ​

✅ 正确性说明 ​

💻 C++ 代码 ​

3.6 渡桥问题（乘船问题） ​

📋 题意 ​

💡 贪心策略 ​

💻 C++ 代码 ​

🌊 简化版：乘船问题（最大搭配） ​

四、优先队列（priority_queue）在贪心中的使用 ​

4.1 priority_queue 基础用法 ​

4.2 自定义比较函数 ​

4.3 优先队列适用的贪心场景 ​

五、贪心不适用的反例 ​

5.1 0/1 背包问题 ​

5.2 硬币问题（非规范货币系统） ​

5.3 判断贪心是否适用的经验法则 ​

六、贪心解题一般步骤 ​

七、📝 实战练习 ​

练习题 1（单选题） ​

练习题 2（判断题） ​

练习题 3（单选题） ​

练习题 4（单选题） ​

练习题 5（判断题） ​

练习题 6（单选题） ​

练习题 7（单选题） ​

练习题 8（编程题） ​

八、📊 考点总结表 ​

⭐ 必背速记卡 ​

第8章贪心算法

🎯 本章学习目标

🗺️ 本章知识图谱

一、引言：什么是贪心算法？

二、贪心算法核心概念

2.1 贪心算法的两个基本要素

2.2 贪心 vs 动态规划

2.3 贪心策略的正确性证明

方法一：交换论证（Exchange Argument）

方法二：反证法

三、经典贪心题型逐个精讲

3.1 区间调度（活动选择问题）

📋 题意

💡 贪心策略

✅ 正确性说明（交换论证）

💻 C++ 代码

3.2 区间覆盖（线段覆盖问题）

📋 题意

💡 贪心策略

✅ 正确性说明

💻 C++ 代码

3.3 找零问题（硬币问题）

📋 题意

💡 贪心策略

✅ 贪心适用条件

💻 C++ 代码（贪心版，适用于规范货币系统）

3.4 合并果子（哈夫曼型贪心）

📋 题意（NOIP 经典题）

💡 贪心策略

✅ 正确性说明

💻 C++ 代码（优先队列实现）

3.5 排队接水

📋 题意

💡 贪心策略

✅ 正确性说明

💻 C++ 代码

3.6 渡桥问题（乘船问题）

📋 题意

💡 贪心策略

💻 C++ 代码

🌊 简化版：乘船问题（最大搭配）

四、优先队列（priority_queue）在贪心中的使用

4.1 priority_queue 基础用法

4.2 自定义比较函数

4.3 优先队列适用的贪心场景

五、贪心不适用的反例

5.1 0/1 背包问题

5.2 硬币问题（非规范货币系统）

5.3 判断贪心是否适用的经验法则

六、贪心解题一般步骤

七、📝 实战练习

练习题 1（单选题）

练习题 2（判断题）

练习题 3（单选题）

练习题 4（单选题）

练习题 5（判断题）

练习题 6（单选题）

练习题 7（单选题）

练习题 8（编程题）

八、📊 考点总结表

⭐ 必背速记卡