csp信奥赛C++高频考点专项训练之贪心算法 --【区间贪心】：雷达安装
csp信奥赛C++高频考点专项训练之贪心算法 --【区间贪心】：雷达安装
题目描述
假设海岸线是一条无限延伸的直线。它的一侧是陆地，另一侧是海洋。每一座小岛是在海面上的一个点。雷达必须安装在陆地上（包括海岸线），并且每个雷达都有相同的扫描范围d dd。你的任务是建立尽量少的雷达站，使所有小岛都在扫描范围之内。
数据使用笛卡尔坐标系，定义海岸线为x xx轴。在x xx轴上方为海洋，下方为陆地。
输入格式
第一行包括2 22个整数n nn和d dd，n nn是岛屿数目，d dd是雷达扫描范围。
接下来n nn行，每行两个整数，为岛屿坐标。
输出格式
一个整数表示最少需要的雷达数目，若不可能覆盖所有岛屿，输出-1。
输入输出样例 #1
输入 #1
3 2 1 2 -3 1 2 1输出 #1
2说明/提示
样例 1 解释
数据范围
对于全部数据，n ≤ 1000 n\le1000n≤1000，$ d \le 2\times 10^4， ，，| x_i | \le 2 \times 10^6， ，，0 \le y_i \le 2\times 10^4$。
思路分析
- 将每个岛屿转化为海岸线（x轴）上的一个区间：对于岛屿坐标 ((x, y))，雷达覆盖半径 (d)，若 (y > d) 则无解；否则区间为[ x − d 2 − y 2 , x + d 2 − y 2 ] [x - \sqrt{d^2 - y^2},\; x + \sqrt{d^2 - y^2}][x−d2−y2,x+d2−y2]。
- 问题变成：在数轴上选最少的点，使每个区间至少包含一个点。经典贪心解法：
- 按区间右端点升序排序。
- 初始化当前雷达位置为− ∞ -\infty−∞，雷达数 (cnt=0)。
- 遍历每个区间，若当前雷达位置小于区间左端点，则必须在此区间右端点放置一个新雷达，(cnt++)，并更新雷达位置为该右端点。
- 输出 cnt，若有岛屿 y > d 则输出 -1。
代码实现
#include<bits/stdc++.h>usingnamespacestd;structseg{doublel,r;}a[1005];//存储区间boolcmp(seg x,seg y){returnx.r<y.r;//按右端点升序}intmain(){intn,d;cin>>n>>d;intx,y;for(inti=0;i<n;i++){cin>>x>>y;if(y>d){cout<<-1;return0;}//无法覆盖doublet=sqrt(d*d-y*y);//半宽a[i].l=x-t;a[i].r=x+t;//计算区间}sort(a,a+n,cmp);//排序intcnt=0;doublelst=-1e9;//cnt雷达数,lst最后雷达位置for(inti=0;i<n;i++){if(lst<a[i].l){//需要新雷达cnt++;lst=a[i].r;//放在右端点}}cout<<cnt;return0;}功能分析
- 输入处理：读取 (n,d) 及每个岛屿坐标，若 (y>d) 直接输出 -1 结束。
- 区间转换：对每个岛屿计算雷达可放置的区间[ x − d 2 − y 2 , x + d 2 − y 2 ] [x-\sqrt{d^2-y^2},\;x+\sqrt{d^2-y^2}][x−d2−y2,x+d2−y2]。
- 贪心覆盖：按区间右端点排序后，维护当前最后一个雷达的位置，若无法覆盖新区间则在该区间右端点新增雷达。
- 输出：最少雷达数。时间复杂度O ( n log n ) O(n\log n)O(nlogn)，空间O ( n ) O(n)O(n)，满足n ≤ 1000 n\le 1000n≤1000的要求。
各种学习资料，助力大家一站式学习和提升！！！
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}【秘籍汇总】（完整csp信奥赛C++学习资料）：
1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：
https://edu.csdn.net/lecturer/7901 点击跳转
2、CSP信奥赛C++竞赛拿奖视频课：
https://edu.csdn.net/course/detail/40437 点击跳转
https://edu.csdn.net/course/detail/41081 点击跳转
3、csp信奥赛高频考点知识详解及案例实践：
CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转
CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转
信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转
4、csp信奥赛冲刺一等奖有效刷题题解：
CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转
信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转
5、GESP C++考级真题题解：
GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转
GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转
GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转
· 文末祝福 ·
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}