GESP5级C++考试语法知识（十三、贪心算法习题：1、双向贪心 2、区间选择贪心）
🍬 第1题：糖果王国的公平分配（双向贪心）
1、🌈 故事开场
（1）在糖果王国里，有一排小朋友站队领棒棒糖 🍭：
（2）每个小朋友都有一个“胃口值”（数字表示）：
👉 胃口越大，说明越想吃糖！
（3）老师要发糖果，规则是：
1️⃣ 每个孩子至少1颗（不能有人没糖 😢）
2️⃣ 如果一个孩子胃口更大，他必须比旁边的人拿更多糖
2、❗ 问题来了
👉 老师想：我最少要给大家分多少糖？
3、🧠 为什么是“贪心算法”？
因为老师的策略是：
👉“我只看眼前邻居，尽量给刚刚够用的糖！”
不多给（节省糖果）
只满足规则（局部最优）
👉 这就是贪心：每一步都做“当前最省”的选择
4、🔍 举个例子
（1）3个小朋友的胃口值：
1 2 2（2）🪜 第一步：先每人1颗糖
糖果：1 1 1（3）👉 从左往右看
规则：右边胃口大 → 糖更多
1 → 2 ✔ → 第二个要多变成：
1 2 1第三个：
2 → 2 ❌ 不需要更多（4）👉 从右往左看（关键！）
因为可能从右边看，可能不满足！
检查：
2 = 2 不需要调整✔ 2 > 1 不需要调整✔保持不变：
1 2 1（已经满足）（5）👉 大家思考下如果是4个小朋友，胃口值是1 3 3 1 ，结果会是怎样呢？
5、🎯 贪心规律总结
👉规则拆分成两个方向：
1️⃣ 左 → 右（处理右比左大）
2️⃣ 右 → 左（处理左比右大）
👉 每一步都只做“刚刚够”的调整！
6、💻参考程序：
#include <iostream> #include <vector> using namespace std; int main() { int n; cin >> n; vector<int> a(n), candy(n, 1); for(int i = 0; i < n; i++) cin >> a[i]; for(int i = 1; i < n; i++) if(a[i] > a[i-1]) candy[i] = candy[i-1] + 1; for(int i = n-2; i >= 0; i--) if(a[i] > a[i+1]) candy[i] = max(candy[i], candy[i+1] + 1); int sum = 0; for(int x : candy) sum += x; cout << sum; }7、💻 代码逐步讲解
vector<int> a(n), candy(n, 1);👉 初始化：
每个人先发1颗（规则1）
🪜 第一轮（左 → 右）
for(int i = 1; i < n; i++) if(a[i] > a[i-1]) candy[i] = candy[i-1] + 1;👉 含义：
如果右边胃口更大：
➡️ 糖 = 左边 + 1（刚刚多一点）
🪜 第二轮（右 → 左）
for(int i = n-2; i >= 0; i--) if(a[i] > a[i+1]) candy[i] = max(candy[i], candy[i+1] + 1);👉 为什么要max？
因为：
左边可能已经有糖了
不能变小！
👉 所以取最大！
🧮 最后统计
int sum = 0; for(int x : candy) sum += x;8、🎯 本题本质
👉 这是一个：
⭐“双向贪心 + 局部调整”模型
🕒 第2题：时间管理大师的挑战（区间贪心）
1、🌈 故事开场
小明报名了很多活动 🎪：
| 活动 | 开始 | 结束 |
|---|---|---|
| A | 1 | 3 |
| B | 2 | 4 |
| C | 3 | 5 |
但问题来了：
👉 活动不能同时参加！（会冲突）
2、❗ 目标
👉 小明想参加最多的活动！
3、🧠 为什么是贪心？
（1）小明的策略是：
👉“我优先选最早结束的活动！”
（2）为什么？
结束早 → 后面时间更空
可以安排更多活动
（3）👉 这题是典型的贪心问题！
4、🔍 实例推演
活动：
(1,3) (2,4) (3,5)🪜 第一步：按结束时间排序
(1,3) (2,4) (3,5)🪜 第二步：开始选
👉 先选 (1,3)
当前结束时间 = 3👉 下一个活动：
(2,4) ❌ 开始2 < 3（冲突） (3,5) ✔ 开始3 >= 3选：
(3,5)👉 最终选了2个！
5、❓ 为什么不能选“开始最早”？
反例：
(1,10), (2,3), (3,4)如果选 (1,10)：
👉 后面全没了 ❌
正确做法：
👉 选结束早的！
6、🎯 贪心规律总结
（1）👉按结束时间排序
（2）👉 每次选：
开始时间 ≥ 当前结束时间7、💻 代码逐步讲解
#include <iostream> #include <algorithm> using namespace std; struct Node { int l, r; }; bool cmp(Node a, Node b) { return a.r < b.r; } int main() { int n; cin >> n; Node a[1005]; for(int i = 0; i < n; i++) cin >> a[i].l >> a[i].r; sort(a, a + n, cmp); int cnt = 0, last = -1e9; for(int i = 0; i < n; i++) { if(a[i].l >= last) { cnt++; last = a[i].r; } } cout << cnt; }8、💻 代码逐步讲解
（1）📦 结构体
struct Node { int l, r; };👉 l = 开始
👉 r = 结束
（2）🔃 排序
sort(a, a + n, cmp);bool cmp(Node a, Node b) { return a.r < b.r; }👉 按结束时间升序！
（3）🧠 贪心选择
int cnt = 0, last = -1e9;👉 last = 上一个活动结束时间
for(int i = 0; i < n; i++) { if(a[i].l >= last) { cnt++; last = a[i].r; } }👉 逻辑：
如果不冲突 → 选
更新结束时间
9、🎯 本题本质
👉 这是一个：
⭐“区间选择贪心（按结束时间排序）”经典模型
🚀 两题对比总结（非常关键！）
| 题目 | 贪心策略 | 本质 |
|---|---|---|
| 🍬 糖果 | 局部最小调整 | 双向贪心 |
| 🕒 活动 | 选结束最早 | 区间贪心 |