csp信奥赛C++高频考点专项训练之贪心算法 --【区间贪心】：雷达安装

csp信奥赛C高频考点专项训练之贪心算法 --【区间贪心】雷达安装题目描述假设海岸线是一条无限延伸的直线。它的一侧是陆地另一侧是海洋。每一座小岛是在海面上的一个点。雷达必须安装在陆地上包括海岸线并且每个雷达都有相同的扫描范围d dd。你的任务是建立尽量少的雷达站使所有小岛都在扫描范围之内。数据使用笛卡尔坐标系定义海岸线为x xx轴。在x xx轴上方为海洋下方为陆地。输入格式第一行包括2 22个整数n nn和d ddn nn是岛屿数目d dd是雷达扫描范围。接下来n nn行每行两个整数为岛屿坐标。输出格式一个整数表示最少需要的雷达数目若不可能覆盖所有岛屿输出-1。输入输出样例 #1输入 #13 2 1 2 -3 1 2 1输出 #12说明/提示样例 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​,xd2−y2​]。问题变成在数轴上选最少的点使每个区间至少包含一个点。经典贪心解法按区间右端点升序排序。初始化当前雷达位置为− ∞ -\infty−∞雷达数 (cnt0)。遍历每个区间若当前雷达位置小于区间左端点则必须在此区间右端点放置一个新雷达(cnt)并更新雷达位置为该右端点。输出 cnt若有岛屿 y d 则输出 -1。代码实现#includebits/stdc.husingnamespacestd;structseg{doublel,r;}a[1005];//存储区间boolcmp(seg x,seg y){returnx.ry.r;//按右端点升序}intmain(){intn,d;cinnd;intx,y;for(inti0;in;i){cinxy;if(yd){cout-1;return0;}//无法覆盖doubletsqrt(d*d-y*y);//半宽a[i].lx-t;a[i].rxt;//计算区间}sort(a,an,cmp);//排序intcnt0;doublelst-1e9;//cnt雷达数,lst最后雷达位置for(inti0;in;i){if(lsta[i].l){//需要新雷达cnt;lsta[i].r;//放在右端点}}coutcnt;return0;}功能分析输入处理读取 (n,d) 及每个岛屿坐标若 (yd) 直接输出 -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​,xd2−y2​]。贪心覆盖按区间右端点排序后维护当前最后一个雷达的位置若无法覆盖新区间则在该区间右端点新增雷达。输出最少雷达数。时间复杂度O ( n log ⁡ n ) O(n\log n)O(nlogn)空间O ( n ) O(n)O(n)满足n ≤ 1000 n\le 1000n≤1000的要求。各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;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标准模板库STLhttps://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 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}