先解释下题目。题目的意思是在一个海上有许多小岛,为了能够探测到这些岛,打算在海岸上建立雷达站(海岸是直的),给出岛的坐标,给出雷达站的覆盖半径,求最少需要多少个雷达站能覆盖所有的小岛。
乍看之下这个题目就是贪心,先算出每个岛在哪个区间范围内建立雷达站能够覆盖到这个岛,排个序,然后每次都取右面坐标就是了,但是这个想法不对,因为总是可以举出反例的(具体的先不谈)。而正确的算法是:要考虑把雷达站放到哪个位置使得包含雷达的区间最多!要不是看其他大牛的blog,我这辈子是够呛能想出来了,呵呵。
写算法的时候要注意,排序完成后,第一个雷达建立在区间的右端,而后一次判断每个区间的左端点,如果在最新建立的雷达右面,那么肯定需要一个雷达,而且也建在区间右端。如果左端点在雷达左面,这个时候要考虑区间的右端在雷达的左面还是右面,如果是右面,那雷达位置就不变,如果在左面,那现在的雷达是覆盖不了的,所以要把雷达放在该区间的右端点!因为这样同时还能覆盖原来的岛,还能覆盖现在的岛!
不多说了,看代码就清楚了
#include <iostream>
#include <cmath>
using namespace std;
double pos[1001][2];
struct In
{
double left,right;
}qujian[1001];
int cmp( const void *a ,const void *b)
{
return (*(In *)a).left >= (*(In *)b).left ? 1 : -1;
}
double wucha = 0.00000001;
int main()
{
int n,d;
int total = 0;
while (cin >> n >> d)
{
bool b = true;
if (n == 0 && d == 0)
break;
if (d <= 0)
b = false;
int i;
for (i = 0; i < n; ++i)
cin >> pos[i][0] >> pos[i][1];
for (i = 0; i < n; ++i)
{
double temp = d*d - pos[i][1] * pos[i][1];
if (temp < 0)
{
b = false;
break;
}
else
{
qujian[i].left = pos[i][0] - sqrt(temp);
qujian[i].right = pos[i][0] + sqrt(temp);
}
}
if (b)
{
qsort(qujian,n,sizeof(qujian[0]),cmp);
double radar = qujian[0].right;
int t = 1;
for (i = 1; i < n; ++i)
{
if (qujian[i].left > radar)
{
++t;
radar = qujian[i].right;
}
else
{
if (qujian[i].right < radar)
radar = qujian[i].right;
}
}
printf("Case %d: %d\n",++total,t);
}
else
{
printf("Case %d: -1\n" ,++total);
}
}
return 0;
}
联系客服