蓝桥杯算法精讲：贪心算法之区间问题深度剖析

目录前言一、贪心算法1.1 区间问题1.1.1 线段覆盖1.1.2 Radar Installation1.1.3 Sunscreen1.1.4 牛栏预定结语 云泽Q个人主页 专栏传送入口: 《C语言》《数据结构》《C》《Linux》《蓝桥杯系列》⛺️遇见安然遇见你不负代码不负卿~前言大家好啊我是云泽Q欢迎阅读我的文章一名热爱计算机技术的在校大学生喜欢在课余时间做一些计算机技术的总结性文章希望我的文章能为你解答困惑~一、贪心算法1.1 区间问题区间问题是另一种比较经典的贪心问题。题目面对的对象是一个一个的区间让我们在每个区间上做出取舍。这种题目的解决方式一般就是按照区间的左端点或者是右端点排序然后在排序之后的区间上根据题目要求制定出相应的贪心策略进而得到最优解。具体是根据左端点还是右端点排序升序还是降序一般是假设一种排序方式并且制定贪心策略当没有明显的反例时就可以尝试去写代码。1.1.1 线段覆盖凌乱的yyy / 线段覆盖解法按照区间左端点从小到大排序当两个区间「重叠」的时候我们必须要舍弃一个。为了能够「在移除某个区间后保留更多的区间」我们应该把「区间范围较大」的区间移除。因此以第一个区间为基准遍历所有的区间如果重叠选择「最小的右端点」作为新的基准如果不重叠那么我们就能多选一个区间以「新区间为基准」继续向后遍历。#includeiostream#includealgorithmusingnamespacestd;typedeflonglongLL;constintN1e610;structnode{LL l;LL r;}a[N];LL n;boolcmp(nodex,nodey){returnx.ly.l;}intmain(){cinn;for(inti1;in;i)cina[i].la[i].r;sort(a1,a1n,cmp);//以第一个区间为右端点第一个区间必选LL ret1;//以第一个区间的右端点为基准向后选择LL right_sidea[1].r;for(inti2;in;i){LL lefta[i].l,righta[i].r;//重叠if(leftright_side){//保留右端点较小的区间right_sidemin(right_side,right);}else{//不重叠ret;right_sideright;}}coutretendl;return0;}1.1.2 Radar InstallationRadar Installation如图所示当一个岛屿的坐标已知其实可以计算出当雷达放在 x 轴的哪段区间时可以覆盖到这个岛屿根据勾股定理得ax的长度 l根号下d2−y2那么雷达所处的范围就是 [x - lx l]。因此针对每一个岛屿我们都可以算出一个能够覆盖它的区间。原问题就变成给定一些区间从中选取一些区间尽量多的重叠区间能够覆盖掉所有的岛屿最少能够选多少个。就从二维平面转化成一维线段#includeiostream#includecmath//开根号用#includealgorithm//sqortusingnamespacestd;//区间数/岛屿数constintN1010;doubled;intn;//存储每个岛屿对应的「雷达可覆盖区间」x轴上的区间structnode{//计算的时候因为涉及开根号所以这里的数据类型是doubledoublel;doubler;}a[N];// 排序比较函数按区间左端点升序排序boolcmp(nodex,nodey){returnx.ly.l;}intmain(){intcnt0;// 记录测试用例的编号Case 1、Case 2...while(cinnd,nd){cnt;//标记是否存在无法覆盖的岛屿y dboolflagfalse;// 遍历所有岛屿计算每个岛屿对应的雷达覆盖区间for(inti1;in;i){doublex,y;cinxy;//岛屿的y坐标超过雷达半径垂直距离已超范围无法覆盖if(yd)flagtrue;// 勾股定理doublelsqrt(d*d-y*y);//计算该岛屿对应的雷达覆盖区间[x-l, xl]a[i].lx-l;a[i].rxl;}coutCase cnt: ;// 如果存在无法覆盖的岛屿直接输出-1if(flag)cout-1endl;else{sort(a1,a1n,cmp);//最少雷达数初始为1至少需要1个雷达覆盖第一个区间intret1;//用第一个区间右端点作为基准判断第二个区间是否与其重叠doublera[1].r;for(inti2;in;i){doublelefta[i].l;doublerighta[i].r;//情况1当前区间与已覆盖区域重叠能被当前雷达覆盖if(leftr){//只有取更小的右端点才能同时覆盖重叠的所有区间rmin(r,right);}//请况2当前区间与已覆盖区域不重叠需要新增雷达else{ret;//新雷达的最优位置为当前区间的右端点rright;}}coutretendl;}}return0;}要点补充为什么把所有区间按左端点 l 从小到大排序。这样我们可以从左到右处理区间保证每次处理的都是当前最靠左的区间不会漏掉任何需要覆盖的区域。while (cin n d, n d)如果括号内有一个逗号隔开的话就是一个逗号表达式其会从左向右执行前面cin n d执行完后当n和d不为0的时候才会继续执行下一步二者为0时while循环跳出1.1.3 Sunscreen1.1.4 牛栏预定结语