一、贪心的使用纪律
贪心每步取眼前最优、不做回溯，正确性无法靠直觉保证。考场纪律：
- 先猜策略：常见排序关键字只有几种——右端点、截止时间、差值、比值、大小。逐个试。
- 小样例验证：手算 2~3 组小数据，策略错会立刻暴露。
- 想交换论证：心里过一遍"交换相邻两个元素不会更优"的证明；说不清楚就慎用。
- 拿不准就加反悔机制：见反悔贪心。
T1 考情：近年 T1 都是"排序 + 一个关键观察"：2024 决斗（双指针）、2025 社团招新（反悔）、2021 廊桥分配（贪心观察）。纯模拟送分时代已过，但套路就这几种。
二、双指针：排序后的免费午餐
数组有序后，很多"找一对 / 找一段"的问题可以用两个指针 O(n) 扫完：
- 对撞指针：一左一右向中间走（两数之和、配对问题）；
- 快慢指针：同向滑动维护一个窗口（滑动窗口、不超过 k 的最长段）。
例（2024 决斗 P11231）：n 只怪兽，第 i 只攻击力 ai。每回合可让一只怪兽攻击另一只：攻击力严格大的一方消灭对方（相等则无法消灭）；每只怪兽至多消灭一只、也至多只被消灭一次。求最少存活几只。
这等价于"最多能配成多少对（强者，弱者）"。排序后双指针：让最弱的未配对怪兽去被"能赢它的最弱怪兽"消灭，能配就配——每只怪兽只扫一次。答案 = n − 配对数，O(n log n) 搞定。
生活类比：掰手腕淘汰赛，每人最多赢一场、输一场。想淘汰最多人，就不能让冠军去打亚军（浪费！），而要让"刚好能赢的人"去赢——大力士要省着用。
排序 + 双指针的识别信号：答案只关心"配对方案"而不关心顺序；数据范围 n ≤ 2×10⁵
三、区间模型三姐妹
以下三个模型是贪心题的"常驻嘉宾"，差别只在问法：
| 模型 | 问题 | 贪心策略 |
|---|---|---|
| 区间调度 | 最多选多少个互不重叠的区间 | 按右端点排序，能选就选 |
| 区间选点 | 最少选几个点，使每个区间都含至少一个点 | 按右端点排序，当前区间还没被覆盖就在其右端点放点 |
| 区间覆盖 | 最少选几个区间覆盖目标线段 [A, B] | 每次在"左端点 ≤ 当前位置"的区间里选右端点最远的 |
真题对照：2024 超速检测 = 区间选点；P1514 引水入城第二问 = 区间覆盖。两者常与 BFS / 模拟复合出现（先求出区间，再贪心）。
四、模板代码（区间选点）
sort(seg + 1, seg + n + 1, [](Seg a, Seg b){ return a.r < b.r; });
int ans = 0; long long last = LLONG_MIN; // 上一个选的点
for (int i = 1; i <= n; i++)
if (seg[i].l > last) { // 当前区间还没被盖住
ans++; last = seg[i].r; // 在右端点放一个新点
}五、易错点清单
- 排序关键字选错：区间模型几乎都是右端点，只有覆盖问题在扫描中比"最远右端点"。
- 严格大于 vs 大于等于：决斗类配对问题差一个等号就会挂一组数据。
- 双指针忘记"每个指针只进不退"，写成双重循环退化成 O(n²)。
- 坐标范围大时
last初值要足够小（用 LLONG_MIN 而非 -1）。
六、练习
- P11231 [CSP-S 2024] 决斗（排序 + 双指针）
- P1514 引水入城（BFS 求区间 + 区间覆盖贪心）
- 真题对照：CSP-S 2024 T2 超速检测（区间选点）
- 进阶：需要"后悔"的贪心 → 反悔贪心