雷达设备

1 题目描述

假设海岸是一条无限长的直线，陆地位于海岸的一侧，海洋位于另外一侧。

每个小岛都位于海洋一侧的某个点上。

雷达装置均位于海岸线上，且雷达的监测范围为 $d$ ，当小岛与某雷达的距离不超过 $d$ 时，该小岛可以被雷达覆盖。

我们使用笛卡尔坐标系，定义海岸线为 $x$ 轴，海的一侧在 $x$ 轴上方，陆地一侧在 $x$ 轴下方。

现在给出每个小岛的具体坐标以及雷达的检测范围，请你求出能够使所有小岛都被雷达覆盖所需的最小雷达数目。

输入格式

第一行输入两个整数 $n$ 和 $d$ ，分别代表小岛数目和雷达检测范围。

接下来 $n$ 行，每行输入两个整数，分别代表小岛的 $x, y$ 轴坐标。

同一行数据之间用空格隔开。

输出格式

输出一个整数，代表所需的最小雷达数目，若没有解决方案则所需数目输出 -1。

数据范围

$1 \le n \le 1000$ , $-1000 \le x, y \le 1000$ 。

输入样例：

输出样例：

2 解析

区间选点 板子。

启发式策略：

区间按右端点升序排序。
对于当前未选点的区间，以它的右端点作为我们选择的点：
1. 之后所有左端点小于该点的区间都被该点覆盖。
2. 对于第一个未被该点覆盖的区间，重复上述操作。

证明：

按照上述做法，我们选择的点都是某个区间的右端点，而且由于区间按右端点排好序了，所以我们选择的点也是排好序的。

只有在当前区间和上一个点所对应的区间是没有交集时，我们才会选择一个新点，所以所有选出的点所对应的区间两两之间没有交集。

找到了 $m$ 个两两之间没有交集的区间，因此我们至少需要选 $m$ 个点，得证启发式策略为最优策略。

完整证明见下文区间选点为什么贪心最优。

int cnt = 0;
sort(seg + 1, seg + n + 1);
double pos = -1e9;
for (int i = 1; i <= n; i ++ )
{
    if (pos + eps < seg[i].l)
    {
        cnt ++ ;
        pos = seg[i].r;
    }
}

3 区间选点为什么贪心最优

题目：Radar Installation AcWing112

对于这个问题的抽象:

多个区间，添加最少点，使得每个区间都含有点。
最少点使得多个区间含有点。
区间选点问题。

3.1 基本思路 $O(n^2)$

区间 $a, b$ 有两种关系：1. 分离 2. 含有公共部分（包含，相交）。

每个区间都可以看成一个集合，这个问题就变成了使用最少的元素，使得每个集合都至少含有一个元素（决策集合）。

对于任意关系的集合 $A_1, A_2, \dots, A_n$ 来说：

情况 1：如果有 $n$ 个集合，且这 $n$ 个集合的交集不为空，那么答案集合就是这 $n$ 个集合的交集。
情况 2： $n$ 个集合的交集是空集，如下图所示，答案集合是两个集合：
结论：当你做出一个答案集合 $X$ 之后，如果能更小（发现和另一个答案集合 $Y$ 有交集，那么答案就是 $X \cap Y$ ），那就更小。

对于某个集合 $A_1$ 来说，如何找到它所对应的答案集合呢？根据上面的结论：

使用集合 $A_1$ 和其他集合 $A_2, A_3, \dots, A_n$ 尝试进行交集运算，得到的最小非空集合就是答案集合。
$A_1 \cap A_i \cap A_j \cap \dots \ne \varnothing$ ， $X = \{A_i \mid A_1 \cap \bigcap A_i \ne \varnothing \}$ ，那么 $X$ 集合里面的元素就是我们所要找的和 $A_1$ 集合交起来非空的那些集合。
这样的话，我们把 $X$ 集合里的元素全部打上标记，从原集合里面去除，在剩余的集合里面再去按照这个方法去寻找。
总体时间复杂度为 $O(n^2)$ 。

3.2 优化 $O(n)$

上面的时间复杂度为 $O(n^2)$ ，那么，还有更快的方法吗？

如果我们可以对所求的集合进行排序，使得属于同一个 $X$ 集合（即 $X$ 集合内部的所有集合相交不为空），例如 A B C D，C B A D。

那么我们就可以从头到尾进行遍历，因为集合的交集运算是一种迭代运算，当我们算到某一步，发现交集为空时，我们就得到了一个答案。

那么这个排序后的序列，后面的问题就可以作为一个整体问题，这显然是一种 DP 或者是分解子问题的思想。

回到这一个区间选点问题，如果我们对区间进行排序（先按照区间的起始位置，然后再按照区间的结束位置），我们能够保证交在一起的区间都在一起吗？

对于排序后的第一个区间 $[a_1, b_1]$ 来说，它和第 2 个区间有两种关系：

情况一：两个区间没有公共部分，则第一个区间和后边的所有的区间都不会有公共部分，此时去除第一个区间之后，问题变成一个新的子问题。
情况二：第一个区间和第 2 个区间有交集（存在公共部分）：
1. 根据上面的推导：则这个答案区间一定是这两个区间的交集 $B$ 。
2. 此时此刻第 1 个区间和第 2 个区间可以从数轴上删除，添加一个新的区间，也就是他们俩的交集 $B$ ，显然并不会影响最终答案。
3. 重复执行操作 2，直到变成情况一，此时就会得到第一个答案区间，也就是区间 $[a_1, b_1]$ 所对应的答案区间。
显然，上面这种操作是递归，根据所学知识，所有的递归都是可以使用数学归纳法来证明（上面的整个过程显然是正确的）。

由此，我们证明完毕我们的贪心过程。

还有一个重要的结论：会枚举每一个区间，所以不会漏。

4 相关题解

暂无相关题解