POJ 1328 Radar Installation 《挑战程序设计竞赛(第2版)》练习题答案

2.2 一往直前！贪心法 区间

POJ 1328 Radar Installation

给定海岛个数、雷达半径以及各海岛坐标，求能覆盖所有海岛的最小雷达数。

贪心策略依然是从左往右，尽量让每颗雷达覆盖最大岛屿数。

对整个题目数据的处理有个思维转换的过程，如果从雷达这个点出发去思考，那么会陷入double无尽的遍历中去。

我的思路是，先对每个海岛求一个区间：能覆盖它的所有雷达的圆心所构成的区间。然后对区间排序，定义一个最右点end，依次延伸end，如果end不在某个区间内，那么消耗一颗雷达，end更新为该区间的最右端，否则end更新为起点在end内的所有区间的最小右端点。

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <limits>
using namespace std;

// 区间
struct Section
{
	double begin;
	double end;
	bool operator < (const Section& b) const 
	{  
		return begin < b.begin;
	} 
};

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
	int n, d, __id;
	__id = 0;
	while(cin >> n >> d && n > 0)
	{
		int result = 0;
		vector<Section> s(n);
		for (int i = 0; i < n; ++i)
		{
			double x, y;
			cin >> x >> y;
			if (result == -1)
			{
				continue;
			}
			if (y > d)
			{
				// 如果y比半径大，一定不能覆盖
				result = -1;
				continue;
			}
			double r = sqrt(d * d - y * y);
			s[i].begin = x - r;
			s[i].end = x + r;
		}

		if (result == -1)
		{
			cout << "Case " << ++__id << ": " << result << endl;
			continue;
		}

		sort(s.begin(), s.end());
		double end = -numeric_limits<double>::max();
		for (vector<Section>::iterator it = s.begin(); it != s.end(); ++it)
		{
			// cout << it->begin << " " << it->end << endl;
			if (end < it->begin)
			{
				++result;
				end = it->end;
			}
			else if (end > it->end)
			{
				end = it->end;
			}
		}

		cout << "Case " << ++__id << ": " << result << endl;
	}
#ifndef ONLINE_JUDGE
    fclose(stdin);
    fclose(stdout);
    system("out.txt");
#endif
    return 0;
}
///////////////////////////End Sub//////////////////////////////////

这里用到了一个很优雅地求double最小值的方法：

double end = -numeric_limits<double>::max();

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 1328 Radar Installation 《挑战程序设计竞赛(第2版)》练习题答案