放牧代码和思想
专注自然语言处理、机器学习算法
    正处于一个非常忙的阶段,抱歉不会经常回应任何联络

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版)》练习题答案

分享到:更多 ()

评论 5

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. #3

    poj上超时了呀

    guo俊7个月前 (01-13)回复
  2. #2

    else if (end > it->end)
    {
    end = it->end;
    }
    这一句不太理解

    奥特曼3年前 (2015-02-27)回复
  3. #1

    其实应该是这个numeric_limits<int>::min()最小,比-numeric_limits<double>::max()还小1.

    Xue-sen3年前 (2014-05-22)回复
    • 不对。浮点数的范围大得多

      一个是-2147483648
      一个是-179769313486231610000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000.000000

      hankcs3年前 (2014-05-23)回复

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机