GESP 7级
贪心策略
7级 · DP/图论/搜索
📖 一句话理解
贪心（Greedy）就是每一步都选当前看起来最好的，不做长远考虑，也不回头。就像你在自助餐里，每次都拿眼前最想吃的菜，不考虑后面还有没有更好的。
💡 为什么重要？
贪心是很多经典算法的核心思想：Dijkstra最短路、Kruskal最小生成树、哈夫曼编码、活动选择……都是基于贪心。但贪心不一定能得到全局最优解，只有满足特定条件的问题才能用贪心。学会判断一个问题能不能用贪心，是7级考试的重要考点。
📋 前置知识
- 排序：sort()函数的使用，以及自定义排序（lambda表达式）
- 基本的逻辑推理：能理解"为什么这样贪是对的"
- 了解 背包问题 会有帮助（对比贪心和DP的区别）
🧠 贪心的两个条件
🔑 什么时候能用贪心？
- 贪心选择性质：局部最优选择能导致全局最优。即"每步选最好的，最终结果就是最好的"。
- 最优子结构：问题的最优解包含子问题的最优解。
⚠️ 注意：不是所有问题都满足这两个条件！不满足时贪心会得到错误答案，需要用DP或搜索。
📐 经典贪心问题
问题1：区间调度（选最多的不重叠区间）
有n个时间段的活动，每个活动有开始时间和结束时间。选最多的活动，使得它们互不重叠。
💡 贪心策略
按结束时间排序，每次选结束最早的活动。为什么？结束越早，留给后面的空间越大。
💻 区间调度代码（逐行注释）
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Interval {
int start, end; // 活动的开始和结束时间
};
int main() {
int n;
cin >> n;
vector<Interval> intervals(n);
for (int i = 0; i < n; i++)
cin >> intervals[i].start >> intervals[i].end;
// 贪心策略：按结束时间从小到大排序
sort(intervals.begin(), intervals.end(),
[](const Interval& a, const Interval& b) {
return a.end < b.end; // 结束早的排前面
});
int cnt = 0; // 已选活动数量
int last_end = -1; // 上一个选中活动的结束时间
for (auto& p : intervals) {
// 如果当前活动的开始时间 >= 上一个活动的结束时间
// 说明不重叠，可以选
if (p.start >= last_end) {
cnt++; // 选这个活动
last_end = p.end; // 更新结束时间
}
// 否则跳过（重叠了，不能选）
}
cout << "最多能选 " << cnt << " 个活动" << endl;
return 0;
}问题2：零钱兑换（贪心不一定对！）
⚠️ 贪心的陷阱：零钱兑换
硬币面值 [1, 3, 4]，凑出6元。
贪心：先选最大的4 → 再选1+1 → 共3枚
最优：选3+3 → 只要2枚
❌ 贪心在这里不是最优的！因为贪心选择性质不满足。这种问题需要用DP。
📊 贪心 vs DP vs 暴力搜索
📝 三种方法对比
- 暴力搜索：尝试所有可能，时间指数级，正确但太慢
- 贪心：每步选最好的，时间快（通常O(n log n)），但不一定正确
- 动态规划：记录子问题答案，时间多项式级，保证正确
做题时的思考顺序：先想贪心能不能用（证明一下）→ 不能就用DP → 再不行就搜索。
🎯 常见贪心策略
💡 需要记住的贪心模式
- 区间调度：按结束时间排序，选最早结束的
- 活动选择：和区间调度类似
- 分数背包：按单位价值（价值/重量）排序，从高到低选（注意：01背包不能贪心！分数背包可以）
- 任务调度：按截止时间排序，优先做紧急的
🚨 易错点
⚠️ 常见错误汇总
- 不证明就用贪心：考试时如果题目要求"证明贪心正确性"，不能只写代码。要说明"为什么局部最优能导致全局最优"。
- 01背包用贪心：01背包不能用贪心！必须用DP。只有分数背包（物品可以部分取）才能贪心。
- 排序方式搞错：区间调度按结束时间排，不是按开始时间！按开始时间排贪心不一定正确。
- 漏考虑边界：第一个区间不需要判断和前一个是否重叠（因为last_end初始化为-1）。
- 贪心和DP搞混：如果题目说"每个物品只能选一次"且不能分割，大概率是DP不是贪心。
🎯 练习建议
📝 循序渐进练习路径
- 先理解贪心的本质：在纸上分析"为什么这样贪是对的"。
- 做经典题目：
- P1803 凌乱的yyy（洛谷区间调度入门）
- P1020 导弹拦截（贪心+二分）
- P1090 合并果子（贪心+优先队列）
- 对比练习：拿同一个问题，分别用贪心和DP做，看什么时候贪心正确什么时候不正确。
- 学会证明：尝试用反证法证明贪心策略的正确性。