[题目概述]
假设海岸是一条无限长的直线,陆地位于海岸的一侧,海洋位于另外一侧。
每个小岛都位于海洋一侧的某个点上。
雷达装置均位于海岸线上,且雷达的监测范围为 d,当小岛与某雷达的距离不超过 d 时,该小岛可以被雷达覆盖。
我们使用笛卡尔坐标系,定义海岸线为 x 轴,海的一侧在 x 轴上方,陆地一侧在 x 轴下方。
现在给出每个小岛的具体坐标以及雷达的检测范围,请你求出能够使所有小岛都被雷达覆盖所需的最小雷达数目。
输入格式
第一行输入两个整数 n 和 d,分别代表小岛数目和雷达检测范围。
接下来 n 行,每行输入两个整数,分别代表小岛的 x,y 轴坐标。
同一行数据之间用空格隔开。
输出格式
输出一个整数,代表所需的最小雷达数目,若没有解决方案则所需数目输出 −1。
数据范围
1 ≤ n ≤ 1000,
−1000 ≤ x, y ≤ 1000
输入样例:
3 2
1 2
-3 1
2 1
输出样例:
2
分析题意
按照题意我们能画出来这个图,就是让我们求,最少几个红圆就能将所有点覆盖。
但是通过这个圆求范围我们是不好求的,可以将其转换一下,变成区间问题,看每个小岛雷达的可安置范围,如果多个小岛的安置范围有重合,那么我们只要安一个雷达就能全覆盖。只有不重合的区间我们才需要安多个雷达
这就是典型的区间贪心问题。
取雷达:我们每次取都是取区间的右端点,因为我们的排序是按照右端点地递增的顺序来排,如果两个区间重合,那么我们取的点一定是在重合的范围内的,如果两个区间没有交集,那么上次取的点一定是在此区间左端点的左边
红色的标记就是我们需要的雷达
完整代码(详细注释)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define x first
#define y second
using namespace std;
typedef pair<double, double> PDD;
const int N = 1010;
int n, d;
PDD seg[N];
int main (){
cin >> n >> d;
// 判断是否有解
bool is_failed = false;
for(int i = 0; i < n; i ++){
int x, y;
cin >> x >> y;
if(y > d){
is_failed = true;
break;
}
double len = sqrt(d * d - y * y);
// 存放的顺序是区间右端点和左端点,方便比较
seg[i] = {x + len, x - len};
}
if(is_failed){
cout << -1;
}else {
// 将区间排序,保证右端点是递增的
sort(seg, seg + n);
int cnt = 0, last = -1e20;
for(int i = 0; i < n; i ++){
// 取雷达条件,
if(last < seg[i].y){
cnt ++;
last = seg[i].x;
}
}
cout << cnt << endl;
}
return 0;
}
- 本题的分享就结束了,此题属于区间贪心的经典问题,可以多思考一下,第一次做应该是想不到的,有问题欢迎留言。