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

前言

大家好啊，我是云泽Q，欢迎阅读我的文章，一名热爱计算机技术的在校大学生，喜欢在课余时间做一些计算机技术的总结性文章，希望我的文章能为你解答困惑~

一、贪心算法

1.1 区间问题

区间问题是另一种比较经典的贪心问题。题目面对的对象是一个一个的区间，让我们在每个区间上做出取舍。

这种题目的解决方式一般就是按照区间的左端点或者是右端点排序，然后在排序之后的区间上，根据题目要求，制定出相应的贪心策略，进而得到最优解。

具体是根据左端点还是右端点排序？升序还是降序？一般是假设一种排序方式，并且制定贪心策略，当没有明显的反例时，就可以尝试去写代码。

1.1.1 线段覆盖

凌乱的yyy / 线段覆盖


解法
按照区间左端点从小到大排序，当两个区间「重叠」的时候，我们必须要舍弃一个。为了能够「在移除某个区间后，保留更多的区间」，我们应该把「区间范围较大」的区间移除。
因此以第一个区间为基准，遍历所有的区间：

• 如果重叠，选择「最小的右端点」作为新的基准；
• 如果不重叠，那么我们就能多选一个区间，以「新区间为基准」继续向后遍历。

#include<iostream>#include<algorithm>usingnamespacestd;typedeflonglongLL;constintN=1e6+10;structnode{LL l;LL r;}a[N];LL n;boolcmp(node&x,node&y){returnx.l<y.l;}intmain(){cin>>n;for(inti=1;i<=n;i++)cin>>a[i].l>>a[i].r;sort(a+1,a+1+n,cmp);//以第一个区间为右端点，第一个区间必选LL ret=1;//以第一个区间的右端点为基准向后选择LL right_side=a[1].r;for(inti=2;i<=n;i++){LL left=a[i].l,right=a[i].r;//重叠if(left<right_side){//保留右端点较小的区间right_side=min(right_side,right);}else{//不重叠ret++;right_side=right;}}cout<<ret<<endl;return0;}

1.1.2 Radar Installation

Radar Installation


如图所示，当一个岛屿的坐标已知，其实可以计算出：当雷达放在 x 轴的哪段区间时，可以覆盖到这个岛屿

根据勾股定理得：ax的长度 l=根号下d²−y²，那么雷达所处的范围就是 [x - l，x + l]。因此，针对每一个岛屿，我们都可以算出一个能够覆盖它的区间。

原问题就变成给定一些区间，从中选取一些区间（尽量多的重叠区间），能够覆盖掉所有的岛屿，最少能够选多少个。就从二维平面转化成一维线段

#include<iostream>#include<cmath>//开根号用#include<algorithm>//sqortusingnamespacestd;//区间数/岛屿数constintN=1010;doubled;intn;//存储每个岛屿对应的「雷达可覆盖区间」（x轴上的区间）structnode{//计算的时候因为涉及开根号，所以这里的数据类型是doubledoublel;doubler;}a[N];// 排序比较函数：按区间左端点升序排序boolcmp(node&x,node&y){returnx.l<y.l;}intmain(){intcnt=0;// 记录测试用例的编号（Case 1、Case 2...）while(cin>>n>>d,n&&d){cnt++;//标记是否存在无法覆盖的岛屿（y > d）boolflag=false;// 遍历所有岛屿，计算每个岛屿对应的雷达覆盖区间for(inti=1;i<=n;i++){doublex,y;cin>>x>>y;//岛屿的y坐标超过雷达半径，垂直距离已超范围，无法覆盖if(y>d)flag=true;// 勾股定理doublel=sqrt(d*d-y*y);//计算该岛屿对应的雷达覆盖区间：[x-l, x+l]a[i].l=x-l;a[i].r=x+l;}cout<<"Case "<<cnt<<": ";// 如果存在无法覆盖的岛屿，直接输出-1if(flag)cout<<-1<<endl;else{sort(a+1,a+1+n,cmp);//最少雷达数，初始为1（至少需要1个雷达覆盖第一个区间）intret=1;//用第一个区间右端点作为基准，判断第二个区间是否与其重叠doubler=a[1].r;for(inti=2;i<=n;i++){doubleleft=a[i].l;doubleright=a[i].r;//情况1：当前区间与已覆盖区域重叠（能被当前雷达覆盖）if(left<=r){//只有取更小的右端点，才能同时覆盖重叠的所有区间r=min(r,right);}//请况2：当前区间与已覆盖区域不重叠，需要新增雷达else{ret++;//新雷达的最优位置为当前区间的右端点r=right;}}cout<<ret<<endl;}}return0;}

要点补充：
为什么把所有区间按左端点 l 从小到大排序。
这样我们可以从左到右处理区间，保证每次处理的都是当前最靠左的区间，不会漏掉任何需要覆盖的区域。

while (cin >> n >> d, n && d)如果括号内有一个逗号隔开的话，就是一个逗号表达式，其会从左向右执行，前面cin >> n >> d执行完后，当n和d不为0的时候才会继续执行下一步，二者为0时while循环跳出

1.1.3 Sunscreen

1.1.4 牛栏预定

结语