本文主要是介绍poj 1328 Radar Installation 贪心 暑假第三题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
去年大一的时候，看到这题，真心感觉自己不会，没思路，今天顺手就打出来了。。
下面的思路是其他博主写的的，拿过来借鉴
思路：该题题意是为了求出能够覆盖所有岛屿的最小雷达数目，每个小岛对应x轴上的一个区间，在这个区间内的任何一个点放置雷达，则可以覆盖该小岛，区间范围的计算用[x-sqrt(d*d-y*y),x+sqrt(d*d-y*y)];这样，问题即转化为已知一定数量的区间，求最小数量的点，使得每个区间内斗至少存在一个点。每次迭代对于第一个区间， 选择最右边一个点， 因为它可以让较多区间得到满足， 如果不选择第一个区间最右一个点（选择前面的点）， 那么把它换成最右的点之后， 以前得到满足的区间， 现在仍然得到满足， 所以第一个区间的最右一个点为贪婪选择， 选择该点之后， 将得到满足的区间删掉， 进行下一步迭代， 直到结束。
代码：
//标准的贪心，有两个注意的地方。1.d<0 无解 2.上界优先权，越小越高，取区间的右顶点更优，选择该点之后，删除满足区间，继续迭代。
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
struct Str
{double x;double y;double left;double right;
};
Str a[10000];
int cmp(Str p,Str q)
{return p.right<q.right;
}
int main()
{int n,m,l=1;while(cin>>n>>m){if(n==0&&m==0)break;int i,k=0;for(i=0; i<n; i++){cin>>a[i].x>>a[i].y;double t=sqrt(m*m-a[i].y*a[i].y);a[i].left=a[i].x-t;a[i].right=a[i].x+t;// cout<<a[i].left<<' '<<a[i].right<<endl;if(a[i].y>m||m<0)k=1;}sort(a,a+n,cmp);if(k==1)cout<<"Case "<<l++<<": "<<-1<<endl;else{i=0;int num=0;while(i<n){num++;double x1=a[i].right;int j;for(j=i+1; j<n;){if(x1>=a[j].left&&x1<=a[j].right){j++;}else{break;}}i=j;}cout<<"Case "<<l++<<": "<<num<<endl;}}return 0;
}
这篇关于poj 1328 Radar Installation 贪心 暑假第三题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
