GESP 5级 · 简单贪心

📖 概念讲解

贪心算法（Greedy）：每一步都选当前最优的方案，期望最终结果也是最优。

核心思路：局部最优 → 全局最优。不需要回溯，不需要枚举所有情况。

⚠️ 关键前提：贪心能用的前提是"贪心选择性质"——每次选局部最优不会导致后续更差的结果。但不是所有问题都能贪心！如果题目问"最少次数"或"最优安排"，先想想贪心能不能用。

典型题型：区间调度、活动选择、买菜砍价、排队分配等。解题套路：先排序，再按顺序贪。

💻 代码示例

经典题：活动安排——n个活动，每个有开始和结束时间，一个人同时只能参加一个，最多能参加几个？

贪心策略：按结束时间排序，每次选结束最早且不冲突的。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    int n; cin >> n;                      // 活动数量
    vector<pair<int,int>> a(n);            // 存放 {结束时间, 开始时间}
    for (int i = 0; i < n; i++) {
        int s, e; cin >> s >> e;          // 读入开始和结束时间
        a[i] = {e, s};                     // 注意：结束时间放前面，方便排序
    }
    sort(a.begin(), a.end());              // 按结束时间升序排序
    int cnt = 0, last = 0;               // cnt=已选数量，last=上一个结束时间
    for (auto& [e, s] : a) {               // 遍历所有活动
        if (s >= last) {                   // 开始时间 ≥ 上一个结束时间才选
            cnt++;                          // 选这个活动
            last = e;                       // 更新结束时间
        }
    }
    cout << cnt << endl;
    // 输入: 4\n1 4\n3 5\n0 6\n5 7  → 输出: 3
}

💡 为什么按结束时间排序？因为结束越早，留给后面的时间越多，后面能选的就更多——这就是"局部最优导致全局最优"的体现。

🧩 互动小测

Q1：活动安排问题中，为什么按结束时间排序而不是按开始时间排序？

Q2：以下哪种问题适合用贪心算法？

🏋️ 动手练一练

📝 编程练习：硬币找零

给定 n 种硬币，面值分别为 a₁, a₂, …, aₙ（每种硬币数量无限），以及目标金额 M。
求最少需要多少枚硬币才能凑出 M。如果无法凑出，输出 -1。

提示：先将硬币面值从大到小排序，每次尽可能多地取当前最大面值的硬币（贪心）。
注意：此贪心策略仅在硬币面值满足特定条件（如 1, 2, 5, 10 等常见面值）时才正确！

参考答案：

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

int main() {
    int n, m;
    cin >> n >> m;                    // n种硬币，目标金额m
    vector<int> coins(n);
    for (int i = 0; i < n; i++)
        cin >> coins[i];              // 读入面值
    sort(coins.rbegin(), coins.rend()); // 从大到小排序

    int cnt = 0;
    for (int c : coins) {
        while (m >= c) {              // 能取就取
            m -= c;                    // 扣掉面值
            cnt++;                     // 硬币数+1
        }
    }
    if (m == 0) cout << cnt << endl;  // 刚好凑完
    else cout << -1 << endl;         // 凑不完
    return 0;
}
// 输入: 3 11\n1 2 5 → 输出: 3 (5+5+1)

要点：排序后从大到小贪，每步尽量取大面值。注意这题的贪心只对特定面值组合正确（如1,2,5），如果面值是1,3,4凑6，贪心给4+1+1=3枚，但最优是3+3=2枚——此时需要用DP。

📝 易错点提醒

🔴 不是所有问题都能贪心！01背包、最短路等用贪心会得到错误答案，要先判断问题是否具有贪心选择性质。
🔴 排序是贪心的灵魂。大部分贪心题第一步都是排序——按结束时间、按性价比、按差值等，别忘了 sort。
🔴 贪心和DP的区别：贪心不回头，选了就选了；DP会考虑所有子问题。能用贪心的问题，DP也能做但更慢；不能用贪心的问题，DP才靠谱。
🔴 硬币找零的坑：面值 1, 2, 5 贪心正确，但换一组面值就不一定了。考试遇到硬币题先看面值是否"标准"。

📘 简单贪心

📖 概念讲解

💻 代码示例

🧩 互动小测

Q1：活动安排问题中，为什么按结束时间排序而不是按开始时间排序？

Q2：以下哪种问题适合用贪心算法？

🏋️ 动手练一练

📝 编程练习：硬币找零

📝 易错点提醒