12 贪心算法（Greedy）

级别标注：GESP 5 级（考级要求）/ CSP-J、NOIP 高频（竞赛进阶：正确性证明、区间问题、哈夫曼、活动安排）。

一、什么是贪心

贪心策略：每一步都做"当前看起来局部最优"的选择，期望得到全局最优。使用前提：局部最优能推导出全局最优（需证明或由题目性质保证）。

重要提醒：不是所有问题都能贪心。无法证明时，需谨慎，可改用 DP 或搜索验证。

二、经典贪心题目

2.1 活动安排（会议室/区间调度）

给定若干区间（开始、结束时间），选最多不重叠的区间。策略：按结束时间升序，优先选最早结束的。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct Seg { int l, r; };      // 区间：左端点 l，右端点 r
// 区间选点/选活动：按结束时间最早贪心
int main() {
    int n; cin >> n;
    vector<Seg> v(n);
    for (int i = 0; i < n; i++) cin >> v[i].l >> v[i].r;
    sort(v.begin(), v.end(), [](const Seg &a, const Seg &b) {
        return a.r < b.r;            // 按结束时间升序（先结束的先选）
    });
    int ans = 0, last = -1;          // last 记录上一个选中区间的结束点
    for (auto &s : v) {
        if (s.l >= last) {           // 与上一个不重叠才能选
            ans++;
            last = s.r;              // 更新结束点
        }
    }
    cout << ans << endl;             // 最多可选区间数
    return 0;
}

2.2 硬币找零（特殊币值可贪心）

当币值是"倍数关系"（如 1、5、10、20、50、100 人民币）时，优先用大面额贪心成立。

#include <iostream>
using namespace std;
int main() {
    int money; cin >> money;
    int coins[] = {100, 50, 20, 10, 5, 1};   // 面额从大到小
    int cnt = 0;
    for (int c : coins) {        // 贪心：能多取大面额就多取
        cnt += money / c;            // 当前面额可用张数
        money %= c;                  // 剩余金额
    }
    cout << cnt << endl;             // 最少硬币数
    return 0;
}

⚠️ 一般币值（如 1、3、4）不能贪心，如 6 用贪心得出 4+1+1（3 枚）但最优是 3+3（2 枚）。此类要用 DP（15 章）。

2.3 区间选点 / 覆盖问题

例：给定若干区间，选尽可能少的点使每个区间都至少有一个点被选中。策略：按右端点升序，每次点在当前最靠右的位置。与活动安排同族。

2.4 哈夫曼编码 / 合并果子

每次取两个最小的合并（第 7 章 priority_queue 示例），保证总的合并代价（带权路径长度）最小。

2.5 多机调度 / 平均等待时间

加工时间短的先处理，总等待时间最短（短作业优先）。

三、贪心的正确性证明思路（进阶）

比赛需能"说服自己"： 1. 交换论证法：证明任意最优解中，若相邻两项不满足贪心顺序，交换后不会变差 → 贪心解不差于最优解。 2. 反证法：假设贪心不是最优，构造矛盾。 3. 归纳法：证明贪心每一步都保留最优解的前缀。

对初学者：先用小数据"对拍"（暴力枚举 vs 贪心）验证，再到题解里学习证明方法。

四、贪心 vs 动态规划

常见误区：题目看起来像贪心但实际需要 DP。若贪心解法被样例 HACK，优先想 DP。

五、易错点 / 常见坑点

• ⚠️ 不要盲目贪心：先证明或测反例。经典反例：01 背包（不能按"单位价值"贪心拿，见 15 章）。
• ⚠️ 区间题排序维度要选对：活动安排按右端点，区间选点本质也按右端点。
• ⚠️ 贪心+贪心的叠加可能互相冲突，注意题目条件。
• ⚠️ 结构体排序没写比较函数导致编译错误或默认错误序。
• ⚠️ 结果可能超 int（如合并果子用 long long）。

六、考级要求 vs 竞赛进阶

• 考级要求（GESP 5 级）：贪心入门题（硬币、活动选择、简单调度）能理解并实现；常以"每次取最小/最大"的直接策略命题。
• 竞赛进阶（CSP-J/NOIP）：区间覆盖、多机调度、哈夫曼、贪心+堆结合、贪心与 DP 的辨析；要求会写证明思路并在笔试中出现"贪心反例判断"。

七、课内练习建议

1. 活动安排 / 排队打水（短作业优先）手推最优解并编程序。
2. 写一个"反例找茬程序"：用小数据暴力枚举，对比贪心结果，找到不可贪心的反例。
3. 阅读 2.2 的币值反例，思考为什么 1、3、4 币值不能贪心。
4. 用优先队列实现哈夫曼（合并果子）。
5. 火车调度/线段覆盖类题目各来一道，练"读题→抽象成贪心模型"。