GESP5级C++考试语法知识（十四、贪心算法（二）区间问题（提高级））

《贪心王国·打点小精灵大作战》 一、故事开场在贪心王国里有一片神秘的区域森林 森林里有很多“魔法区间”比如 [1,5] [2,6] [4,7] 危机来了每个区间里都有怪物 国王下令⚠️ 每个区间必须至少放2个守护点‍♂️ 小勇士的任务 放尽量少的点 但要满足每个区间 ≥ 2个点 二、让学生思考汉克老师问 点放在哪里比较好 学生纷纷说放左边放中间放右边 三、关键发现贪心思想汉克老师说 如果你把点放在右边…… 会不会更容易被后面的区间用到 结论点尽量往右放 四、一起玩一个例子区间[1,4] [2,5] [3,6] 第一步排序按右边 已经排好了[1,4] → [2,5] → [3,6]‍♂️ 第二步处理第一个区间 [1,4] 需要 2 个点我们放 3 和 4靠右 现在发生什么这两个点在 [1,4] ✔在 [2,5] ✔在 [3,6] ✔ 结果 后面两个区间也被“顺便解决了” 五、最终答案 只用了2个点 六、总结规律1、 核心策略每次补点都往区间右边放2、 为什么 因为 越靠右 → 越容易帮助后面的区间 七、算法步骤✅ 第1步排序按右端点 谁结束早先处理谁✅ 第2步一个区间一个区间看✅ 第3步如果这个区间不够2个点 就补点✅ 第4步补在哪里 放在rightright-1✅ 第5步这些点可以“帮助后面的区间” 八、参考程序#include iostream #include algorithm using namespace std; // 定义区间 struct Interval { int left; // 左端点 int right; // 右端点 int need; // 还需要几个点初始为2 }; // 排序规则按右端点从小到大 bool cmp(Interval a, Interval b) { if (a.right ! b.right) return a.right b.right; else return a.left b.left; } int main() { int n; cin n; Interval a[10005]; // 输入 for (int i 0; i n; i) { cin a[i].left a[i].right; a[i].need 2; // 每个区间需要2个点 } // 排序 sort(a, a n, cmp); int answer 0; // 选了多少个点 // 遍历每个区间 for (int i 0; i n; i) { // 如果这个区间还缺点 while (a[i].need 0) { // 我们选择点优先选右端点 int chosen_point; if (a[i].need 2) chosen_point a[i].right - 1; // 第一个点 else chosen_point a[i].right; // 第二个点 answer; // 选了一个点 // 用这个点去“帮助”后面的区间 for (int j i; j n; j) { if (a[j].left chosen_point chosen_point a[j].right) { if (a[j].need 0) a[j].need--; } } } } cout answer endl; return 0; } 八、最容易犯错的地方❌ 错误1点放左边 ❌ 很亏 后面用不到❌ 错误2不排序 ❌ 会乱 贪心会失败❌ 错误3忘记“要2个点” ❌ 有学生只放1个❌ 错误4不会“共享点” ❌ 以为每个区间都要重新放 实际 一个点可以帮多个区间 九、课堂小游戏 游戏1你来放点区间[1,3] [2,4] [3,5] 学生们 你会放哪里 游戏2对比 放左边 vs 放右边学生发现右边更强 十、背诵口诀区间要点多全部往右挪越靠右越值钱 十一、本课总结同学们终于学会了✨ “最强打点术”同学们发现 一个点不只是一个点 而是可以影响很多区间汉克老师笑着说“这就是贪心的智慧——用最少的资源做最多的事情。”