🍬 第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、🌈 故事开场

小明报名了很多活动 🎪：

但问题来了：

👉 活动不能同时参加！（会冲突）

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、🎯 本题本质

👉 这是一个：

⭐“区间选择贪心（按结束时间排序）”经典模型

🚀 两题对比总结（非常关键！）