基础贪心专题雷达安置WA90分

常规
1

9. 雷达安置

XJOI - 题目ID：9559选做题100分

最新提交：

Wrong Answer

90 分

历史最高：

Wrong Answer

90 分

时间限制: 100ms

空间限制: 131072kB

题目描述

题目描述：

假设海岸线是一条无限延伸的直线。它的一侧是陆地，另一侧是海洋。每一座小岛是在海面上的一个点。雷达必须安装在陆地上（包括海岸线），并且每个雷达都有相同的扫描范围d。你的任务是建立尽量少的雷达站，使所有小岛都在扫描范围之内。注意，建立雷达站的点的坐标必须为整数。

数据使用笛卡尔坐标系，定义海岸线为x轴。在x轴上方为海洋，下方为陆地。

[image]

输入格式：

第一行包括2个整数n和d，n是岛屿数目，d是雷达扫描范围。

接下来n行为岛屿坐标，均为整数。

输出格式：

一个整数表示最少需要的雷达数目，若不可能覆盖所有岛屿，输出“-1”。

样例输入：

3 2 1 2 -3 1 2 1

样例输出：

2

约定：

n<=1000,d<=20000

-210^6<=xi<=210^6

0<=yi<=20000

代码：

`#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
struct node{
	int l,r;
}a[100005];
bool cmp(node x,node y){
	if(x.r!=y.r) return x.r<y.r;
	else	return x.l<y.l;
}
vector<int>v;
int main(){
	int n,d;
	cin>>n>>d;
	int x,y;
	long long cnt=0;
	for(int i=1;i<=n;i++){
		cin>>x>>y;
		if(y<=d){
			cnt++;
			a[cnt].l=x-sqrt(d*d-y*y);
			a[cnt].r=x+sqrt(d*d-y*y);
		}
		else{
			cout<<"-1";
			return 0;
		}
	}
	sort(a+1,a+cnt+1,cmp);
	long long sum=0;
	bool flag; 
	for(int i=1;i<=cnt;i++){
		flag=false;
		for(int j=0;j<v.size();j++){
			if(v[j]>=a[i].l&&v[j]<=a[i].r){
				flag=true;
				break;	
			}
		}
		if(!flag){
			v.push_back(a[i].r); 
			sum++;
		}
	}
	cout<<sum;
	return 0;
}`
2 个赞
2

区间贪心的方式可以优化，可以考虑以每个区间的结束位置排序，遍历排序后的序列，在第一个区间结束位置安装第一个雷达，后续每遍历一个区间，看一下起始位置是否比上一个雷达位置小，否则雷达数++，整体遍历一遍就可以，时间复杂度o(n)

5 个赞
3

本蒟蒻根据题目现场手码了一个代码（样例过了）：

#include<bits/stdc++.h>
using namespace std;
int n,d,ans;
struct node{
    double x,y;
    bool vis=0;
}a[1010];
bool cmp(node p,node q){
    return p.y<q.y;
}
int main(){
    cin>>n>>d;
    for(register int i=0;i<n;i++){
        double p,q,m;
        cin>>p>>q;
        if(q>d){cout<<-1;return 0;}
        m=sqrt(d*d-q*q);
        a[i].x=p-m,a[i].y=p+m;
    }
    sort(a,a+n,cmp);
    for(int i=0;i<n;i++){
        if(a[i].vis)continue;
        ans++;
        a[i].vis=1;
        for(int j=0;j<n;j++) if(!a[j].vis&&a[i].y>=a[j].x)a[j].vis=1;
    }
    cout<<ans;
    return 0;
}
2 个赞