本文主要是介绍POJ 1328 Radar Installation 贪心，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：海中有许多岛屿，现在要再海岸上建立雷达，但是每个雷达的覆盖半径只有d，为了使每个岛屿都被覆盖到，求最少需要多少雷达。（建立坐标系，海岸为 x 轴，岛屿以坐标形式给出。
题解：先求出每个岛屿的被覆盖范围，即当岛屿被可以被覆盖时，雷达可以建立的最左位置及最右位置。将每个岛屿的最左位置升序排列，然后贪心求解。
题解：先求出每个岛屿的被覆盖范围，即当岛屿被可以被覆盖时，雷达可以建立的最左位置及最右位置。将每个岛屿的最左位置升序排列，然后贪心求解。
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <iostream>
using namespace std;
struct p
{
double left;
double right;
} pos[1001];
int cmp ( const void* a, const void* b )
{
p *c, *d;
c = (p*)a, d = (p*)b;
return c->left > d->left ? 1 : -1;
}
int main()
{
int n, res, i, test = 0;
double d, current, x, y;
while ( cin >> n >> d && n && d )
{
res = 0;
for ( i = 0; i < n; i++ )
{
cin >> x >> y;
if ( y > d )
res = -1;
else
{
pos[i].left = x - sqrt(d*d-y*y);
pos[i].right = x + sqrt(d*d-y*y);
}
}
if ( res == -1 )
{
cout << "Case " << ++test << ": -1" << endl;
continue;
}
qsort ( pos, n, sizeof(p), cmp );
current = pos[0].right;
res = 1;
for ( i = 1; i < n; i++ )
{
/* 当岛屿 i 的最左位置比前一个岛屿的最右位置还大时，说明前一个岛屿不可能与它后面的岛屿共享雷达，那么需要为前一个岛屿建立一个雷达 */
if ( pos[i].left > current )
{
res++;
current = pos[i].right;
}
else
{
/* 当岛屿 i 在前一个岛屿的被覆盖范围之内时，为了使 i 被覆盖到， current 应该改为岛屿 i 的右侧 */
if ( pos[i].right < current )
current = pos[i].right;
}
}
cout << "Case " << ++test << ": " << res << endl;
}
return 0;
}这篇关于POJ 1328 Radar Installation 贪心的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
