算法代表着用系统的方法描述解决问题的策略机制，北京大学《算法基础》课程将带你一一探索枚举、二分、贪心、递归、深度优先搜索、广度优先搜索、动态规划等经典算法，体会他们巧妙的构思，感受他们利用计算解决问题的独特魅力。顺利完成本课程，你将不但能够掌握这些算法的原理，还能够对这些算法进行灵活应用以及准确实现。本课程的中的编程任务，将充分训练你的思维能力和动手能力，促成全面、缜密思考问题的习惯。达到本门课程的要求，即意味者你具备了初步的算法基础和较强的编程实现能力。
雷达安装问题
Loading...
来自 北京大学 的课程
算法基础
259 评分
从本节课中
二分与贪心
二分法是在有序或单调的区间中快速寻找答案的有效方法，当数据量很大适宜采用该方法。所谓贪心算法，即总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。但是，贪心算法对很多问题都能得到整体最优解。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。本模块将介绍二分与贪心这两个对很多问题都非常有效的算法策略。
与讲师见面
Jiaying Liu 刘家瑛, Ph.D.Associate Professor
Institute of Computer Science & Technology
郭 炜讲师
北京大学信息科学技术学院教学所
大家好，我们来看一下二分与贪心算法的第三道例题，
所谓雷达安装问题。那么这个题目描述呢是讲的这样的一个故事， 说一共有 n
个小岛位于 x 轴之上， 那么 x 轴呢你可以认为是所谓的海岸，
而 x 轴上方呢表明是海洋，所谓在海洋内部有一些 n 个小岛。
那么现在呢你需要在海岸上去建立雷达， 每个雷达的覆盖半径呢为 d，
也就是说每个雷达能覆盖距离它不超过 d 的所有的点。
那么我们现在要求什么呢？求出在海岸上建立最少的雷达数目，
使得可以覆盖所有的小岛，那么认为每一个小岛都是一个点。
那么题目实际上就是说我们在 x
轴上面， 那么它认为这就是所谓的海岸线，海岸线上面有很多若干不同位置的小岛，
那么我如果建立一个雷达，这个雷达的半径如果是 d，是 d，
那么我画一个圆，我所涵盖的这些岛的位置就能够在我雷达的范围内。
如果还有一些岛呢本身不在我的范围内，那我就需要再建立一个雷达然后再去
这个覆盖起来，才能把所有的小岛覆盖住。
那么程序的输入呢包含了若干组。
每一组呢都是两个数，一个是 n，一个是 d。
那么 n 是小于 1000 大于 1 的，那么 n 呢和 d 呢 分别表示的是小岛的数量和雷达的半径。
那么接下来的 n 组自然就是表征这个 n
个小岛的坐标， 之后呢程序的这个输入以 0 0 作为结束。
那么对于输出来讲的话呢，每一组数据输出一行，也就是最小的雷达数。
否则呢如果是无解就输出 负 1，这个题目的描述其实还是蛮简单的。
那么程序的这个样例的输入呢有两组。
第一组呢 case 1，一共有 3 个小岛，并且呢雷达的半径是 2。
那么下面呢就是依次这三个小岛对应的 x y 坐标。
那么此外呢就是 case 2，那么case 2 呢
本身它是由 1 个小岛和这个相应的雷达的这个
d 的这个半径。那么我们可以看到相应的输出的话 对于 case 1 来讲，我需要建立两个雷达。
而对于 case 2 来讲，我只需要一个雷达，因为我只有一个小岛，且它在我的雷达范围，覆盖范围之下。
那么我们来看，这张图就是 case 1 的一个 示意图，那么我们会看到说我们一共有
3 个小岛， 分别是这个 ( 1 2) 点 P1，这个
(-3 1) 点 P2 和 (2 1) 点
P3。那么我们知道我们的这个雷达的覆盖半径是 2，
所以如果我在 1 这个位置上去建立一个雷达，那么它的覆盖面积
覆盖范围呢正好在这个 P1 的正上方，所以半径是 2，可以盖住。
而相应的这个 P3 呢就在我的这个覆盖范围内。
那么 P2 呢相比就跑得太远了，所以我需要在其这个对应的位置再去
建立一个雷达来覆盖整个我的这个所谓的小岛所在的范围。
那么对于这样的一个题目，我们来分析解题思路的话，如果直接从这个
找寻最少的雷达所覆盖所有小岛这样的一个问题出发，
其实分析起来呢会比较的复杂，因为整个雷达所 处的位置，它可以遍布整个
x 轴的任何一个位置， 但是它和这个小岛之间的关系，雷达与雷达之间的这个
重叠都是非常复杂，并没有什么直观的这种关系可以来进行
这个确定。那么反过头来如果我们从 小岛入手，因为小岛的 x
y 坐标都是确定的， 并且呢我们也知道雷达为了覆盖这个小岛所提供的这个半径的长度，
那么我们就能够考虑每个小岛被覆盖所需雷达的位置。
什么叫被覆盖所需雷达的位置呢？我们说我们去考虑， 比如说以这个小岛，第 i
个小岛为例，我们有一个雷达范围 是可以把这个
i 所覆盖到的， 那么我们这个雷达现在这里，我们这个
覆盖范围跟 x 轴实际上是有一个， 这个圆呢本身是有一个，这样的一个
线段的一个交，那么它的左边 这个 left 和 right，
这段区间范围内的 任何一个点上，那么它都可以满足
建一个雷达就一定能够覆盖着小岛i。因为在其最远的这个边界上 left
和 right 上面呢，它的这个 半径就是我们所说的雷达所能够触及的最大的半径 d。
所以我们说对于这样的一个问题，小岛 i
它所对应覆盖的，能够覆盖住它的雷达的位置是什么呢？ 它是必须位于
x 轴的 s[i].left， 到 s[i].right
之间，也就是我们这里画的这一段线段的这个长度。
那么有了这样的一个考虑之后，问题就转化了，我们为每一个小岛 对应
x 轴上的一段线段，s[i].left 到 s[i].right，
现在我们要求出最少的点使得所有的线段都被覆盖到。我们原来
是去求在哪儿架雷达覆盖所有岛，现在呢 我们反过头来我们认为说每一个小岛要被覆盖，
必须是在相应的这个线段上去架设一个雷达，
那么既然要取得最小的这个雷达数，那么也就是说让所有这些线段能够
被最少的点使得这些所有线段被覆盖到，这当然是一个典型的贪心问题。
我们说我们要怎么贪心呢，我们要由小到大去将线段
按左端点进行排序。那么正常情况下我们去比较一个线段，两个线段之间的关系，
我们是既要考虑左端点，又要考虑右端点。
那为了让后续的问题变得简单，我们对左端点先进行排序，这样我们就只用去讨论右端点。
那么我们贪心怎么干呢？贪心的策略就是找到一个点
使其能够覆盖尽可能多的线段。
那么我们依次加入一个线段 i，
我们首先说说怎么样能够覆盖尽可能多的线段？也就是说我有 第
i 个小岛，第 i+1 个小岛，甚至有第 i+2
个小岛， 那么这些小岛它都有一个重叠的部分，
那么这些重叠的部分上如果我去架设一个雷达，那么它就可以涵盖这些所有的小岛。
所以我现在要找的事儿就是尽量去找那个点， 使得其位于线段上最多的，就能够它能够出现在
最多的线段上，所以我们每一次加入一个新的线段 i 之后，
如果这个线段 i 与当前的所有线段，j
到 i-1 是没有公共交点的，那说明什么？
说明它跟之前其他的小岛所对应的那个 x 轴上的线段是没有交集的，也就是说
不管在那些地方建多少个雷达，它都不能够去覆盖我当前这个线段 i 所对应的那个小岛。
所以就说明需要新建，那么发现什么呢？发现说我的 s[i].left，也就是我新进来的这个线段本身，
它的这个 left 点如果大于我之前一系列的这个线段中间的
右端点，从 s[j].right 一直到
s[i-1].right，我们在这一系列的这个 right
中间去找寻到 它 min 的这个点，什么呢？因为它为了保证
是有公共交点的，那么我们只需要去 考虑它最小的那么一个 right 的点。
否则的话呢就说明我在当前原来的这个公共集合上
所建立的这个雷达是你新 加入的这个线段没有办法这个触及到的。
所以呢我们说你要考虑在这些最右端的点中间最小的
这个点，因为我们的公共端点，公共的这段区间是位于最小的这个 right
的 左边，所以呢我们说当你新加入的这个线段的左边如果
它大过最小的那个，现有其他线段 的右端点，最小的右端点的话，我们就需要新建雷达。
否则就把它加入到当前的线段当中，是吧？否则什么意思？就说明我新加入的这个线段i
它是和其他的这一系列线段是有公共交集的，是吧？
那么实现的时候我们呢因为已经对左端点进行了排序，所以我们只需用
维护当前集合当中右端点中间最小的那个值来进行判断就可以了。
那么判断新加入的这个线段的左端点是否大于这个右端点集合中间的最小值，是吧？
如果小于等于，说明有公共交点，那么加入当前集合，更新这个
最右端的最小值，我们要看一看新加入这一端点是不能够使得这个
右端的这个最小值变得更小了，对吧？因为它可能会需要的这个位置更紧致，
那么如果大于的话，说明什么，说明新加入的这个线段i呢，它和刚才一系列的集合是没有- 交点的，
必须要通过新建雷达才能满足覆盖。
所以我们说我们最重要的呢就是要去写一个函数，叫Solve，
这个函数Solve呢它做的事，就是首先第一点是让它的这个
线段呢按左端点，注意是左端点来进行排序， 排序完了之后呢，我们就要去取第一个
设置当前第一个雷达，是吧？第一个雷达，完了之后呢我们要把当前的这个
now，是吧？当前集合的这个右端点最小值置为谁？当然是置为我
第一个雷达所覆盖的这个s[0].right， 之后我要做的事就是每次新加入进来一个线段i，是吧？那新加入进来的这个线段i呢
它会让它的左端点是去now比，注意now是当前集合的这个
右端点的最小值，如果这个now
本身是大于等于left，说明什么，说明新加入进来的这个线段是和之前是有公共交点的，
那么我们只需要去看一看now和这个s[i].right谁更小， 是吧？如果发现这个s[i].right呢它更小，
那么呢我们就要去更新now,是吧？否则呢，就不动，就相当于取这个min。
那么除此之外我们发现说如果这个s.，s[i].left如果是大于now的，那它说- 明什么？
说明我们当前需要加入一个新的雷达，是吧？那么这个时候我们就要让我们的这
ans呢++，同时呢让我的now更新为s[i].right。最后return呢就是我
这个需要得到的这个雷达数。
那么有了这样的一个最重要函数的分析之后，我们当然写程序就非常简单了。
我们定义了一个struct，来定义这个线段Node。
那么它有一个left值，有一个right值，完了之后呢， 我们还有相应的这个T，n，d，来去标记这个相应的输入，
然后完了之后去建立一个这样Node的一个数组s。
那么要注意就是我们要让你的Node按照左端点来由小
这个到大来进行排序，所以呢我们说我们要去重载这个
operator<，让它按照这个左边端点a.left和b.left来进行比较，
之后就是我们刚才看到的这个最核心的Solve这个函数， 我们说呢我们去排序是吧？sort因为已经重载好了operator
<， 完了之后我们依次去遍。首先第一点就是建立第一个雷达，要更新now，
完了之后我们输入进来这个i，然后每一个新的线段呢去跟now比，注意是去，它的lef- t去比，
然后去更新我当前的这个now值，看看它哪一个是更min的，如果是原来的这个
集合的右端点，还是我当前输入线段的右端点，
否则的话说明呢我现在当前的这个雷达呢都盖不住，那么我们就要让雷达数++，然后去更新- now的这个值。
所以最后return 这个ans呢，就是这个雷达的数量。
那么最后的话我们就是这个main函数，是吧？主要是完成相应的这个输入， 我们呢每次会输入这个对应的这个
雷达的这个小岛的数量和相应雷达覆盖的这个范围半径d，是吧？
然后呢如果是0==0情况，就说明整个程序要结束。
完了之后呢我们就依次去输入这个小岛 的位置x和y，把它放进相应的这个
我们的这个Node里头，是吧？这个Node s数组。那么要注意就是我们要去
计算相应的left和right，是吧？我们要利用这个x和y， 以及和d的这个关系来进行计算。那么如果有小岛的距离
x已经大于d，说明什么，说明你现在的这个 小岛的位置不管我在这个地方怎么架雷达，它的这一段
半径d，从小岛出发都达到不了我的海岸线，对吧？这段是虚的。
所以说明什么？说明我们不可能通过建立，在海岸线上去建立雷达来完成这样的这个任务。
所以呢我们就要去这个输出相应的这个-1，是吧？ 否则的话呢，我们就正常地输出我们对应每个Case，
所得到Solve这个函数，所得到的构建雷达的数量。
所以这就是关于这个雷达安装问题的一个题目求解的一个思路。
