贪心算法讲义
贪心算法讲义
【适合阶段】CSP-J 一等奖以下,已掌握 C++ 基础语法和简单排序
【前置知识】sort 排序、结构体、数组、循环
【建议课时】6 讲,每讲 1.5~2 小时
目录
| 讲次 | 主题 | 例题 | 难度 |
|---|---|---|---|
| 第 1 讲 | 排序贪心——"排个序,顺着拿" | 1216 书架、1307 排队接水、ZYF037 两地调度 | ⚪⚪⚪ |
| 第 2 讲 | 区间调度——"按结束时间排" | 1311 活动选择、2597 无重叠区间2、ZYF053 无重叠区间1 | 🔴⚪🟡 |
| 第 3 讲 | 优先队列——"每次都取最小的两个" | ZYF040 连接木棍、B1752 合并果子、ZYF058 IPO | ⚪🟠🟠 |
| 第 4 讲 | 拦截导弹——"找不到就新开一组" | 1310 拦截导弹、B1229 拦截导弹系统数 | 🟠🟠 |
| 第 5 讲 | 综合技巧——多服务台、自定义排序、数学贪心 | B1228 排队打水、ZYF036 最大数、ZYF052 砍竹子 | 🟠🔴🔴 |
| 第 6 讲 | 进阶挑战——扫描线、双指针、记忆化 | ZYF041 会议室、ZYF055 最多会议、8030 纪念品分组、ZYF039 橘子 | ⚪⚪🔵🟡 |
第 1 讲:排序贪心——"排个序,顺着拿"
本课目标
- 理解"排序 + 贪心"的基本模式
- 掌握按不同方向排序的贪心(升序 vs 降序)
- 学会记录原始编号避免信息丢失
核心思想
很多贪心问题只需要做一件事:把数据排个序,然后按顺序处理。
关键在于排什么、按什么方向排——这取决于你的目标。
例题 1:1216 书架 ⚪
题目
有 头奶牛(),第 头高度为 。书架高 。奶牛可以叠罗汉,总高度达到 即可。问最少需要几头奶牛?
思考
目标:用最少的奶牛达到高度 。那每次应该选哪头?
直觉:每次都选最高的!因为高的奶牛能更快帮你堆到目标高度。
贪心策略
- 按高度从大到小排序
- 从最高的开始累加,直到总高度
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 20005;
int h[N];
int main() {
int n, b;
cin >> n >> b;
for (int i = 1; i <= n; i++) cin >> h[i];
sort(h + 1, h + n + 1, greater<int>()); // 从大到小
int sum = 0, cnt = 0;
for (int i = 1; i <= n; i++) {
sum += h[i];
cnt++;
if (sum >= b) break;
}
cout << cnt << endl;
return 0;
}小结
这就是最朴素的贪心:目标明确 → 每步选最优 → 达成目标就停。
例题 2:1307 排队接水 ⚪
题目
个人排队接水(),第 人接水耗时 。求一种排队顺序,使平均等待时间最小。输出排队方案和平均等待时间(保留两位小数)。
思考
假设排好队后,接水时间依次为 :
- 第 1 人等 0 分钟
- 第 2 人等 分钟
- 第 3 人等 分钟
- 第 人等 分钟
总等待时间
系数 越来越小!所以小的数应该放在前面,乘大的系数;大的数放后面,乘小的系数。
直觉:接水快的人先接,后面的人就不用等太久。
贪心策略
- 按接水时间从小到大排序
- 排序时记录原始编号,否则输出不了排队方案
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
struct Person {
int id; // 原始编号
int t; // 接水时间
} a[N];
bool cmp(Person x, Person y) {
return x.t < y.t; // 从小到大
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i].t;
a[i].id = i;
}
sort(a + 1, a + n + 1, cmp);
double total = 0, wait = 0;
for (int i = 1; i <= n; i++) {
cout << a[i].id << " ";
total += wait; // 当前这个人等了 wait 分钟
wait += a[i].t; // 更新累计等待
}
cout << endl;
printf("%.2f\n", total / n);
return 0;
}关键技巧
🔑 用结构体绑定"数据"和"编号",排序后还能知道原来的位置。
例题 3:ZYF037 两地调度 ⚪
题目
个人,每人去 A 市花费 ,去 B 市花费 。要求 A、B 各去恰好 人。求最小总花费。
思考
如果所有人都去 A,总花费 。现在需要把其中 个人改去 B。
第 个人从 A 改到 B,费用变化是 。这个值可能是负数(改了更便宜)或正数(改了更贵)。
直觉:优先把"改去 B 省钱最多"(即 最小)的人改去 B。
贪心策略
- 假设全去 A
- 计算
- 按 从小到大排序
- 前 人改去 B,后 人留 A
手动模拟
输入:(共 4 人,A、B 各去 2 人)
人 a_i b_i diff = b_i - a_i
1 10 20 +10
2 30 200 +170
3 400 50 -350
4 30 20 -10
按 diff 排序后:人3(-350), 人4(-10), 人1(+10), 人2(+170)
前2人去B:人3(50) + 人4(20) = 70
后2人留A:人1(10) + 人2(30) = 40
总花费 = 110代码
#include <bits/stdc++.h>
using namespace std;
const int N = 20005;
struct Person {
int a, b, diff;
} p[N];
bool cmp(Person x, Person y) {
return x.diff < y.diff; // diff 小的先去 B
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> p[i].a >> p[i].b;
p[i].diff = p[i].b - p[i].a;
}
sort(p + 1, p + n + 1, cmp);
int ans = 0;
for (int i = 1; i <= n; i++) {
if (i <= n / 2) ans += p[i].b; // 前 n 人去 B
else ans += p[i].a; // 后 n 人留 A
}
cout << ans << endl;
return 0;
}💡 思考:输入中的 是总人数,去 A、B 各 人。注意读题!
本讲小结
| 题目 | 排序方式 | 方向 | 新技巧 |
|---|---|---|---|
| 1216 书架 | 按高度 | 降序 | 贪心最基础形态 |
| 1307 排队接水 | 按时间 | 升序 | 结构体保留编号 |
| ZYF037 两地调度 | 按差价 | 升序 | 转换视角(全去A再改) |
一个规律:第 1 讲的贪心都很"直给"——想清楚"按什么排"就直接排序,没有复杂的后续操作。
第 2 讲:区间调度——"按结束时间排"
本课目标
- 掌握区间调度的经典贪心模板
- 区分"端点接触算/不算重叠"的处理差异
- 学会"正难则反"的转化思想(求最少移除 → 求最多保留)
核心思想
给你一堆区间,要你选最多的不重叠区间。记住一句话:
按结束时间排序,每次选最早结束且不冲突的。
为什么不是按开始时间排? 因为选"结束最早"的,给后面的区间留出最多空间。
例题 1:1311 活动选择 🔴
题目
个活动(),每个有起始时间 和结束时间 。同一时间只能进行一个活动。求最多能安排几个活动。
贪心策略
- 按结束时间升序排序
- 初始化 第一个活动的结束时间,
- 遍历后续活动:如果 (不冲突),选它,更新
⚠️ 本题中 不算冲突(前一个结束的那一刻下一个刚好开始是可以的)。
手动模拟
11 个活动,排序后:
1: [1, 4] ← 选,last=4
2: [3, 5] ← 3<4,冲突,跳过
3: [0, 6] ← 已过,跳过
4: [5, 7] ← 5≥4,选,last=7
5: [3, 8] ← 3<7,冲突,跳过
6: [5, 9] ← 5<7,冲突,跳过
7: [6, 10] ← 6<7,冲突,跳过
8: [8, 11] ← 8≥7,选,last=11
9: [8, 12] ← 8<11,冲突,跳过
10:[12, 14] ← 12≥11,选,last=14
11:[2, 13] ← 已过,跳过
最多安排 4 个 ✓代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
struct Act { int l, r; } a[N];
bool cmp(Act x, Act y) { return x.r < y.r; }
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i].l >> a[i].r;
sort(a + 1, a + n + 1, cmp);
int ans = 1, last = a[1].r;
for (int i = 2; i <= n; i++) {
if (a[i].l >= last) { // 不冲突(端点接触可以)
ans++;
last = a[i].r;
}
}
cout << ans << endl;
return 0;
}例题 2:2597 无重叠区间2 ⚪
题目
给定 个区间,求最少移除几个区间,使剩余区间互不重叠。
注意:本题中 和 不算重叠(端点接触是可以的)。
思考
"最少移除"听着不好算。但换个角度想:
🔑 最少移除数 = 总数 - 最多保留数
这不就变成 1311 了吗!按结束时间排序贪心,算最多能保留几个,再用 一减就行。
代码(核心部分与 1311 完全相同)
// ... 排序部分同上 ...
int keep = 1, last = a[1].r;
for (int i = 2; i <= n; i++) {
if (a[i].l >= last) { keep++; last = a[i].r; }
}
cout << n - keep << endl; // 移除数 = 总数 - 保留数例题 3:ZYF053 无重叠区间1 🟡
题目
和 2597 几乎一样,但有一个关键区别: 和 算重叠!求最多能选几个区间。
对比
| 1311 活动选择 | 2597 无重叠2 | ZYF053 无重叠1 | |
|---|---|---|---|
| 端点接触 | 不重叠 | 不重叠 | 算重叠 |
| 条件 | |||
| 求 | 最多选几个 | 最少移几个 | 最多选几个 |
唯一的区别就是条件从 >= 变成了 >!
// 只有这一处不同!
if (a[i].l > last) { // 注意:> 而不是 >=
ans++;
last = a[i].r;
}本讲小结
| 题目 | 端点接触 | 条件 | 求什么 |
|---|---|---|---|
| 1311 活动选择 | 不重叠 | >= | 最多选 |
| 2597 无重叠2 | 不重叠 | >= | 最少移 |
| ZYF053 无重叠1 | 算重叠 | > | 最多选 |
🔑 区间调度题的差异往往只有一行代码!关键是读懂"端点接触算不算重叠"。
第 3 讲:优先队列——"每次都取最小的两个"
本课目标
- 理解哈夫曼合并的贪心原理
- 掌握 STL priority_queue 的用法(小根堆 / 大根堆)
- 学会"排序预处理 + 堆动态维护"的组合模式(IPO)
核心思想
有些问题需要反复取最小值来操作。如果每次都用 sort,复杂度太高。优先队列(堆)可以:
- 取最小值:
- 插入:
小根堆声明(别写反了):
priority_queue<int, vector<int>, greater<int>> pq; // 小根堆,top() 最小
priority_queue<int> pq; // 大根堆,top() 最大(默认)例题 1:ZYF040 连接木棍的最低费用 ⚪
题目
根木棍,长度 。每次选两根连接,成本为两根长度之和,连接后变成一根新木棍(长度为两者之和)。直到剩一根。求最小总成本。
思考
假设有三根木棍长度 :
- 方案 A:先合并 a+b,再合并 (a+b)+c → 成本 = (a+b) + (a+b+c) = 2a+2b+c
- 方案 B:先合并 b+c,再合并 a+(b+c) → 成本 = (b+c) + (a+b+c) = a+2b+2c
因为 最小,方案 A 的总成本更小。
直觉:每次都选最短的两根合并。这样短木棍被反复合并的次数多(反正它短,代价小),长木棍被合并的次数少。
贪心策略
- 所有木棍入小根堆
- 每次取两根最短的,合并,成本累加,新木棍入堆
- 重复直到堆中只剩一根
手动模拟
sticks = [2, 3, 4](排序后:2, 3, 4)
初始堆: [2, 3, 4]
取出 2+3=5, 成本+5, 堆: [4, 5]
取出 4+5=9, 成本+9, 堆: [9]
总成本 = 5 + 9 = 14 ✓代码
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, x;
cin >> n;
priority_queue<int, vector<int>, greater<int>> pq;
for (int i = 1; i <= n; i++) {
cin >> x;
pq.push(x);
}
int ans = 0;
while (pq.size() > 1) {
int a = pq.top(); pq.pop();
int b = pq.top(); pq.pop();
ans += a + b;
pq.push(a + b);
}
cout << ans << endl;
return 0;
}例题 2:B1752 合并果子 🟠
题目
种果子(),每种 个。每次合并两堆,代价为两堆之和。求最小总代价。
思路
和上一题完全一样! 只是换了个场景(木棍 → 果子)。
// 代码与 ZYF040 完全相同,只有变量名和读入方式的细微差异🔑 如果一道题让你反复"合并两个东西,代价是它们之和",那就是哈夫曼合并模型。
例题 3:ZYF058 IPO 🟠
题目
个项目,每个有利润 和启动成本 。初始资金 ,最多做 个项目。每完成一个项目,利润加入资金。求最大最终资本。
思考
这个题复杂一些——不是所有项目一开始都能做,随着资金增长才能解锁更多项目。
直觉:每一步都做"当前资金够启动的、利润最大的"项目。
算法流程
- 把项目按启动成本从小到大排序
- 用一个大根堆存"当前能做的所有项目的利润"
- 进行最多 轮:
- 把所有成本 当前资金的项目利润加入堆
- 取堆顶(最大利润),加入资金
- 如果堆空,退出
以样例为例:n=3, k=2, w=0
projects: [p=1,c=0], [p=2,c=1], [p=3,c=1]
排序后不变
第1轮:资金0,解锁项目0(c=0≤0),堆:[1]
取堆顶1,资金=0+1=1
第2轮:资金1,解锁项目1,2(c=1≤1),堆:[2,3]
取堆顶3,资金=1+3=4
最终资金=4 ✓代码
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
struct Project {
int profit, cost;
} a[N];
bool cmp(Project x, Project y) {
return x.cost < y.cost; // 按成本从小到大
}
int main() {
int n, k, w;
cin >> n >> k >> w;
for (int i = 1; i <= n; i++) cin >> a[i].profit;
for (int i = 1; i <= n; i++) cin >> a[i].cost;
sort(a + 1, a + n + 1, cmp);
priority_queue<int> pq; // 大根堆,存利润
int idx = 1;
while (k--) {
while (idx <= n && a[idx].cost <= w) {
pq.push(a[idx].profit);
idx++;
}
if (pq.empty()) break;
w += pq.top();
pq.pop();
}
cout << w << endl;
return 0;
}🔑 排序预处理 + 大根堆动态选最大,这是处理"逐步解锁资源"问题的经典组合。
本讲小结
| 模型 | 堆类型 | 策略 |
|---|---|---|
| 合并木棍 / 果子 | 小根堆 | 每次取最小的两个合并 |
| IPO | 大根堆 | 每次选能做的利润最大的项目 |
🧠 记忆口诀:"合并用小,选优用大"
第 4 讲:拦截导弹——"找不到就新开一组"
本课目标
- 掌握"贪心维护序列"的思维模式
- 理解"最佳适配"(找≥当前值且最小的)策略
核心思想
有一串数依次到来,你要把它们分配到尽量少的组里,每组内要满足某种单调性。
策略:每来一个数,在已有的组里找"最合适的"放进去。实在找不到,就新开一组。
例题 1:1310 拦截导弹问题 🟠
题目
拦截系统第一发可打任意高度,之后每发不能高于前一发。输入一行 个导弹高度(,没有先给 ),求最少需要几套系统。
思考
每来一个导弹,我们要决定用哪套系统拦截。系统拦截后,"剩余能力"会变小(因为下一发不能高于这一发)。
直觉:在能拦截当前导弹的系统中,选剩余能力最小的(即系统高度 ≥ 导弹高度且最接近的那个)。
为什么? 把"刚好够"的系统用掉,把能力更强的系统留给后面更高的导弹。
手动模拟
导弹序列:[389, 207, 155, 300, 299, 170, 158, 65]
导弹 389:没有系统,新建 sys1=[389]
导弹 207:sys1=389≥207,选 sys1,sys1=207
导弹 155:sys1=207≥155,选 sys1,sys1=155
导弹 300:sys1=155<300,不够!新建 sys2=[300]
导弹 299:sys1=155<299,sys2=300≥299,选 sys2,sys2=299
导弹 170:sys1=155<170,不够!sys2=299≥170,选 sys2?...等等——170 能被 sys2(299) 拦截,但 sys2 因此降为 170。还有更好的选择吗?sys1(155) 不够。
...实际上 170 被 sys1 拦不了,被 sys2 拦了,sys2=170
导弹 158:sys1=155<158,不够!sys2=170≥158,sys2=158
导弹 65:sys1=155≥65,选 sys1,sys1=65
最终:sys1=65, sys2=158,共2套系统 ✓代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int sys[N]; // sys[i] 表示第 i 套系统当前能拦截的最高高度
int cnt = 0; // 系统数量
int main() {
int h;
// 输入是一行整数,没有给 n,用 while(cin>>h)
while (cin >> h) {
// 在已有系统中找最佳匹配:≥h 且最小的
int best = -1;
for (int i = 1; i <= cnt; i++) {
if (sys[i] >= h) {
if (best == -1 || sys[i] < sys[best]) {
best = i;
}
}
}
if (best != -1) {
sys[best] = h; // 用这套系统拦截
} else {
cnt++;
sys[cnt] = h; // 新增一套系统
}
}
cout << cnt << endl;
return 0;
}例题 2:B1229 拦截导弹的系统数量求解 🟠
题目
和第 1 题完全一样,只是输入格式不同——先给 ,再给 个数。
int n, h;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> h;
// 后面逻辑完全一样
}🔑 两道题本质一样,唯一的区别就是输入格式。
本讲小结
| 步骤 | 操作 |
|---|---|
| 1 | 遍历每个新元素 |
| 2 | 在已有组中找"最佳匹配"(≥ 当前值且最小) |
| 3 | 找到了 → 更新那组的值 |
| 4 | 找不到 → 新开一组 |
第 5 讲:综合技巧——多服务台、自定义排序、数学贪心
本课目标
- 多服务台贪心的分配策略
- 自定义排序规则(非数值比较)
- 数学分析辅助贪心决策
例题 1:B1228 排队打水问题 🟠
题目
个人, 个水龙头(,)。每人打水耗时 。求所有人花费的最少总时间。每人花费 = 排队时间 + 打水时间。
思考
和第 1 讲的"排队接水"很像,但现在是多服务台。
直觉:打水快的人先打,且尽量均匀分配到各水龙头。
贪心策略
- 按打水时间从小到大排序
- 维护 个水龙头的"当前累计时间"
- 每次把下一个人分配給累计时间最小的水龙头
手动模拟
n=4, r=2, t=[2, 4, 5, 6]
水龙头1: 0 → 来人(2)→ 此人花费0+2=2, 龙头1累计=2
水龙头2: 0 → 来人(4)→ 此人花费0+4=4, 龙头2累计=4
水龙头1累计(2)最小 → 来人(5)→ 此人花费2+5=7, 龙头1累计=7
水龙头2累计(4)最小 → 来人(6)→ 此人花费4+6=10, 龙头2累计=10
总花费 = 2+4+7+10 = 23 ✓代码
#include <bits/stdc++.h>
using namespace std;
const int N = 505;
int t[N], tap[105]; // tap[j] 表示水龙头 j 的当前累计时间
int main() {
int n, r;
cin >> n >> r;
for (int i = 1; i <= n; i++) cin >> t[i];
sort(t + 1, t + n + 1); // 从小到大
int ans = 0;
for (int i = 1; i <= n; i++) {
// 找当前累计时间最小的水龙头
int pos = 1;
for (int j = 2; j <= r; j++) {
if (tap[j] < tap[pos]) pos = j;
}
ans += tap[pos] + t[i]; // 排队时间 + 打水时间
tap[pos] += t[i];
}
cout << ans << endl;
return 0;
}💡 也可以用优先队列维护水龙头,但 直接遍历完全够用。
例题 2:ZYF036 最大数 🔴
题目
给定 个非负整数,重新排列(每数不可拆分)使组成的数最大。输出这个最大数。
思考
不能直接按数值大小排!比如 [10, 2]:数值上 10 > 2,但拼接 "102" < "210"。
直觉:比较两个数 和 时,看 和 (字符串拼接后比较)。
贪心策略
bool cmp(string a, string b) {
return a + b > b + a; // a 拼 b > b 拼 a,则 a 应在前
}特判
如果全是 0(如 [0, 0, 0]),排序后拼接是 "000",应输出 "0"。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
string a[N];
bool cmp(string x, string y) {
return x + y > y + x;
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + n + 1, cmp);
if (a[1] == "0") { // 最大的是"0",说明全0
cout << 0 << endl;
return 0;
}
for (int i = 1; i <= n; i++) cout << a[i];
cout << endl;
return 0;
}例题 3:ZYF052 砍竹子 🔴
题目
一根长度为 的竹子,砍成若干段(每段正整数),使各段乘积最大。结果对 取模。
数学分析
可以通过数学归纳法证明:
| 最优拆法 | 乘积 | |
|---|---|---|
| 2 | 不拆(或 1+1) | 2 |
| 3 | 不拆 | 3 |
| 4 | 2 + 2 | 4 |
| 5 | 3 + 2 | 6 |
| 6 | 3 + 3 | 9 |
| 7 | 3 + 4 | 12 |
| 8 | 3 + 3 + 2 | 18 |
规律:尽可能多地拆出 3。如果剩 4,拆成 2×2(不拆成 3+1,因为 3×1=3 < 2×2=4)。
算法流程
- 如果 ,直接返回
- ,
- 如果 :
- 如果 :(少拆一个 3,留 4 拆成 2×2)
- 如果 :
- 使用快速幂取模
代码
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
// 快速幂:计算 a^b % MOD
long long qpow(long long a, int b) {
long long res = 1;
while (b) {
if (b & 1) res = res * a % MOD;
a = a * a % MOD;
b >>= 1;
}
return res;
}
int main() {
int n;
cin >> n;
if (n <= 3) {
cout << n << endl;
return 0;
}
int cnt = n / 3, rem = n % 3;
long long ans;
if (rem == 0) {
ans = qpow(3, cnt);
} else if (rem == 1) {
ans = qpow(3, cnt - 1) * 4 % MOD;
} else {
ans = qpow(3, cnt) * 2 % MOD;
}
cout << ans << endl;
return 0;
}本讲小结
| 题目 | 技巧 | 关键词 |
|---|---|---|
| B1228 排队打水 | 多服务台分配 | 每次选最空闲的 |
| ZYF036 最大数 | 自定义排序 | a+b > b+a |
| ZYF052 砍竹子 | 数学推导 | 尽可能拆 3,余 4 拆 2×2 |
第 6 讲:进阶挑战
本课目标
- 综合运用前面所学的技巧
- 接触扫描线、双指针、记忆化搜索等进阶思想
例题 1:ZYF041 会议室 ⚪
题目
给定 个会议的时间 ,求同时进行的最多会议数(即最少需要几个会议室)。
思考
这和第 2 讲的"活动选择"不同——活动选择是"一个会议室能容纳几个",本题是"需要几个会议室"。
直觉(扫描线):把每个会议拆成两个事件——"开始"(+1人)和"结束"(-1人),按时间排序后扫描。
算法
- 把所有"开始"和"结束"作为事件,按时间排序(时间相同则结束先于开始)
- 扫描事件,遇到开始 +1,遇到结束 -1
- 过程中最大人数就是最少会议室数
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 20005;
pair<int, int> e[N * 2]; // {时间, 类型(+1开始/-1结束)}
int m = 0;
int main() {
int n, l, r;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> l >> r;
e[++m] = {l, 1}; // 开始
e[++m] = {r, -1}; // 结束
}
sort(e + 1, e + m + 1); // 时间相同时-1在前(先结束后开始)
int cur = 0, ans = 0;
for (int i = 1; i <= m; i++) {
cur += e[i].second;
ans = max(ans, cur);
}
cout << ans << endl;
return 0;
}例题 2:ZYF055 最多可以参加的会议数目 ⚪
题目
个会议 ,你可以在期间任意一天参加。每天最多 1 个会议。求最多参加几个。
思考
这个题比区间调度更灵活——你不一定要"全程参加",只要选一天就行。
直觉:每天在"今天能参加的会议"中,选结束最早的。这样把后面的时间留给更多会议。
算法
- 按开始时间排序
- 用小根堆维护"当前可参加的会议的结束时间"
- 逐天扫描:加入今天开始的会议,移除已过期的,参加结束最早的
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
struct Event { int l, r; } a[N];
bool cmp(Event x, Event y) { return x.l < y.l; }
int main() {
int n;
cin >> n;
int maxDay = 0;
for (int i = 1; i <= n; i++) {
cin >> a[i].l >> a[i].r;
maxDay = max(maxDay, a[i].r);
}
sort(a + 1, a + n + 1, cmp);
priority_queue<int, vector<int>, greater<int>> pq;
int idx = 1, ans = 0;
for (int day = 1; day <= maxDay; day++) {
// 加入今天开始的会议
while (idx <= n && a[idx].l <= day) {
pq.push(a[idx].r);
idx++;
}
// 移除已过期的
while (!pq.empty() && pq.top() < day) pq.pop();
// 参加结束最早的
if (!pq.empty()) {
pq.pop();
ans++;
}
}
cout << ans << endl;
return 0;
}例题 3:8030 纪念品分组 🔵
题目(NOIP 2007 普及组)
件纪念品,每组最多 2 件,每组价格之和 。求最少分组数。
思考
每组最多 2 件的限制很关键。
直觉:排序后用双指针——最便宜的搭配最贵的("大带小")。如果配不了,贵的自己一组。
算法
- 排序
- 左指针 (最便宜),右指针 (最贵)
- 如果 :配对,++, --
- 否则:最贵的单独一组,--
- 直到
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 30005;
int a[N];
int main() {
int w, n;
cin >> w >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + n + 1);
int l = 1, r = n, ans = 0;
while (l <= r) {
if (l == r) { ans++; break; }
if (a[l] + a[r] <= w) { l++; r--; }
else { r--; }
ans++;
}
cout << ans << endl;
return 0;
}例题 4:ZYF039 吃到N个橘子的最少天数 🟡
题目
个橘子,每天选择:
- 吃 1 个
- 如果 ,吃 个(剩一半)
- 如果 ,吃 个(剩 1/3)
求最少天数。
⚠️ 贪心陷阱
直觉上,"能除 3 就除 3"好像最快。但:
n=10:贪心 10→9(减1)→3(除3)→1(除3)→0,共 4 天?不对,10→9 吃1个需要1天,9 吃 2×9/3=6 个剩 3 需要 1 天...
仔细算:n=10
- 不能除 3(10%3=1),不能除 2
- 只能吃 1 个 → 9(1天)
- 9%3=0,吃 6 个剩 3(1天)
- 3%3=0,吃 2 个剩 1(1天)
- 吃 1 个(1天)
- 总共 4 天 ✓
但对于 n=10,贪心:10→吃1→9→除3剩3→除3剩1→吃1→0,4 天。和最优一样,但 n=100 时可能不一样。
⚠️ 直接贪心可能不是最优!应该用记忆化搜索。
正确解法
优化:不一步步减 1,而是直接减到能被 2 或 3 整除:
#include <bits/stdc++.h>
using namespace std;
unordered_map<int, int> memo;
int dfs(int n) {
if (n <= 1) return n;
if (memo.count(n)) return memo[n];
return memo[n] = 1 + min(dfs(n/2) + n % 2, dfs(n/3) + n % 3);
}
int main() {
int n;
cin >> n;
cout << dfs(n) << endl;
return 0;
}💡 严格来说这道题不属于纯贪心——它属于记忆化搜索 / DP。放在这里是作为一个反例:不是所有"每次选最优操作"的题都能用贪心!
本讲小结
| 题目 | 进阶技巧 | 一句话 |
|---|---|---|
| ZYF041 会议室 | 扫描线 | 开始+1,结束-1,取峰值 |
| ZYF055 最多会议 | 堆+扫描 | 每天选结束最早的 |
| 8030 纪念品分组 | 双指针 | 排序后"大带小" |
| ZYF039 橘子 | 记忆化搜索 | 贪心的反例——需要搜索 |
附录 A:全部题目难度对照表
| 颜色 | 含义 | 题目 |
|---|---|---|
| ⚪ | 暂无评定 | 1216, 1307, ZYF037, ZYF040, ZYF041, ZYF055, 2597 |
| 🔴 | 入门(红) | 1311, ZYF036, ZYF052 |
| 🟠 | 普及-(橙) | B1228, B1752, B1229, 1310, ZYF058 |
| 🟡 | 普及/提高-(黄) | ZYF053, ZYF039 |
| 🔵 | 提高+/省选-(蓝) | 8030 |
附录 B:贪心解题 Checklist
做一道贪心题,按以下步骤检查:
附录 C:进阶阅读
学完这个讲义后,可以继续学习:
- 哈夫曼编码(合并果子的实际应用:文件压缩)
- 最小生成树 Kruskal(图论贪心:每次选最小的边)
- Dijkstra 最短路(图论贪心:每次选距离最小的点)
- 反悔贪心(允许"反悔"的进阶贪心技巧,CSP-S 内容)
