专题4 · 贪心（二）
贪心（一）讲的是「排序 + 取最值」，本讲升级到区间类贪心：
把二维问题降维成一维、把冲突关系建模成区间选点——两道真题带你掌握「问题转化」这一关键能力。
本讲你要带走的三件事
① 会降维
把「二维圆覆盖矩形」用勾股定理压成一维线段覆盖，有效覆盖长度 = 2√(r²−1)。
② 会建模
把「冲突对不能同框」翻译成「区间内必须放一个断点」，即区间选点问题。
③ 会选点
区间选点的固定贪心：按右端点升序，取未命中区间的右端点。
知识地图（承接专题3）
专题3
排序贪心：优惠券 / 平均分配
本讲①
区间覆盖：喷水装置
本讲②
区间选点：照相
共性
排序 → 取当前最优 → 累加
贪心四步法（沿用专题3）
1分解子问题：把全局目标拆成一次次「选一个」。
2确定贪心策略：按什么键排序、每次取哪个。
3求子问题最优：实现「取当前最优」这一步。
4堆叠全局最优：累加 / 拼接成答案。
🆕 本讲新增两类题型
- 区间覆盖：用最少的区间盖满一条线段（喷水装置）。策略：按覆盖长度降序，每次取能延伸最远的。
- 区间选点：选最少的点，使每个区间至少含一个点（照相）。策略：按右端点升序，取未命中区间的右端点。
P1159 · 喷水装置
📖 题意
草坪 长 20 米、宽 2 米。在横中心线上放喷水装置，每个装置湿润以它为中心、半径 R_i 的圆。装置位置可任意选择，问全部湿润最少要几个。
2√(r²−1)（勾股定理）。r ≤ 1 的装置有效覆盖 ≤ 0，无法湿润草坪，直接丢弃。5 个：2 3.2 4 4.5 6 → 答案 2（11.83 + 8.77 ≥ 20）。喷水装置 · 代码走读
#include <iostream> #include <vector> #include <cmath> #include <algorithm> using namespace std; int main(){ int n; cin>>n; vector<double> len; for(int i=0;i<n;i++){ double r; cin>>r; if(r<=1.0) continue; // ① 排除无效装置 len.push_back(2.0*sqrt(r*r-1.0)); // ② 降维 } sort(len.rbegin(),len.rend()); // ③ 覆盖长度降序 const double L=20.0; double sum=0; int cnt=0; for(size_t i=0;i<len.size();i++){ sum+=len[i]; cnt++; if(sum+1e-9>=L) break; // ④ 已盖满 } cout<<cnt<<"\n"; return 0; }
🔍 四步对应
- 分解：每次选「一个装置」来延长已湿润的长度。
- 策略：每次取当前能延伸最远的（有效长度最大）。
- 求子最优：排序后从头取。
- 堆叠：长度累加，达 20 即停。
sum >= 20 可能因精度差一点点而多算一个装置；用 sum + 1e-9 >= L 更稳。喷水装置 · 累加覆盖模拟器
P2207 · 照相 [USACO13OPEN Photo B]
📖 题意
n 头奶牛排成一列编号 1..n。每张照片是连续一段，每头牛至少入镜一次；有 k 对关系不好的牛，不能出现在同一张照片。求最少照片数。
(a,b)（设 a<b）→ 必须在它们之间放一个断点（照片分界），断点位置需落在区间 [a, b−1]。[a, b−1] 至少含一个点。n=7：(1,3)(2,4)(5,6) → 区间 [1,2][2,3][5,5] → 断点 2、5 → 答案 3。a < b，读入后要先交换；a == b 的退化对直接忽略。照相 · 代码走读
struct Seg{ long long l,r; }; bool cmp(Seg a,Seg b){ if(a.r!=b.r) return a.r<b.r; // 右端点升序 return a.l<b.l; } int main(){ long long n; int k; cin>>n>>k; vector<Seg> segs; for(int i=0;i<k;i++){ long long a,b; cin>>a>>b; if(a>b) swap(a,b); // ① 规范化 if(a==b) continue; segs.push_back({a,b-1}); // ② 断点区间 } sort(segs.begin(),segs.end(),cmp); // ③ 按右端点升序 long long last=-1; int cuts=0; for(size_t i=0;i<segs.size();i++){ if(segs[i].l>last){ // ④ 尚未命中 last=segs[i].r; cuts++; // 取右端点 } } cout<<cuts+1<<"\n"; // ⑤ 照片数 return 0; }
🔍 为什么取「右端点」
区间选点的贪心：处理按右端点升序排好的区间，若当前区间还没被已选的点命中，就选它的右端点——右端点越靠右，越可能顺便命中后面的区间，所以是最「划算」的选择。
区间左端点 ≤ 上一个断点，就说明已被覆盖，跳过。a、b 做整数比较，不需要开数组；区间数 ≤ 1000，排序开销极小。照相 · 区间选点模拟器
两题对比：同样是排序，键不同
💧 喷水装置（区间覆盖）
- 目标：用最少的装置盖满 20 米。
- 排序键：有效覆盖长度降序。
- 每步：取能延伸最远的。
- 停止：累计 ≥ 20。
📷 照相（区间选点）
- 目标：用最少的断点命中所有区间。
- 排序键：区间右端点升序。
- 每步：取未命中区间的右端点。
- 收尾：断点数 + 1。
易错辨析 & 当堂检测
💡 易错辨析
照相题中，冲突对 (a,b)（a<b）对应的断点区间是？
📝 当堂检测
喷水装置中，半径 r=1.0 的装置应该？
double 并留 1e-9 余量；照相要先把 a,b 交换成 a<b，且答案是「断点数 + 1」。一道题 100 分是分档给的——不会正解也要先拿保底
复赛一道题的 100 分由十几到二十几个测试点组成， 前面几档专门为「没想出正解的人」准备。四道题各拿 30~40 分， 加起来往往就是一等奖和二等奖的分界。
① 特判档：先别想算法，看数据范围表
题目给的数据范围表就是出题人给你的送分清单。看到「n = 1」「只有一组数据」这类一行，
就先写个 if 直接输出答案。2 分钟换 5~10 分，全场最划算。
② 暴力档：按题意最直白地写一遍
多重循环、DFS 全枚举、朴素 O(n³)……不要优化，只要保证最小那档全对。 它既是保底分，又是后面对拍的标尺——没有它你无法证明正解是对的。
③ 特殊性质档：题目里那句「若……」
常见的送分性质：数据已经有序、所有值完全相同、规模小到可以 O(n²)、 只出现一种类型。题目写出来就是让你拿的，专门写一份即可。
④ 正解档：思路定了，就赢了八成
考场上的时间几乎都花在想思路上，不是写代码。写完先跑样例， 再用第 ② 档的暴力版造小数据对拍——这是唯一能证明你思路对的办法。
本讲 2 道题，各自的四档怎么走
喷水装置 · SPRINKLER
第1档 · 2 分钟
所有 R_i ≤ 1 → 一个都盖不住，直接按无解分支输出
第2档 · 8 分钟
枚举装置的所有子集判断能否盖满，n ≤ 20 时 2ⁿ 稳过
第3档 · 10 分钟
按半径从大到小排序逐个放（贪心雏形，能拿不少分）
第4档 · 15 分钟
转成区间 [x−√(R²−1), x+√(R²−1)]，按左端点排序做区间覆盖
照相 · PHOTO
第1档 · 2 分钟k == 0（没有冲突对）→ 1 张照片就够
第2档 · 8 分钟
枚举所有分段方案 2^(n−1)，n ≤ 20 稳过
第3档 · 10 分钟
冲突对全是相邻牛 → 退化成简单的「断点计数」
第4档 · 15 分钟
从左到右贪心：能延伸就延伸，遇到冲突就在这里断开
0–5 分钟 读题 + 圈出数据范围表里最小的那几档 → 5–15 分钟 写完第 1、2 档并先交一次（保住 20~30 分）→ 15–40 分钟 冲第 3、4 档 → 40–50 分钟 造小数据对拍、检查
freopen 与文件名。椰程锦囊 · 区间类贪心三步自检
① 是覆盖还是选点？
要「盖满一段」→ 覆盖（按长度降序）；要「戳中每个区间」→ 选点（按右端点升序）。
② 排序键对了吗？
这是区间贪心唯一的胜负手。写之前先说清「按什么排、为什么」。
③ 收尾 +1 了吗？
选点题：断点数 + 1 = 段数/照片数。漏了就差 1。
double 与 1e-9；② P2207 照相：注意 a,b 交换、退化对、答案 +1。两题均已生成 Hydro 题包，可直接导入「椰程信奥当堂测评」。