(贪心) – POJ1328

1.概述

原题的意思是,给定两个整型数字n(1<=n<=1000)和一个d(表示雷达的识别距离)。然后接下来的n行分别有两个数x,y表示岛I(i)的坐标(x,y)其中个i(1<=i<=n),你的目标是求可以覆盖所有岛屿的最少的雷达数量(雷达只能放在x轴上)。

2.我的想法

首先利用一个结构体point, 其中每一个x,y,mixx和maxx分别表示横坐标,纵坐标,以d为半径的且以圆心在x轴的雷达的位置的最小值以及最大值。

然后可以通过排序points(比较minx的位置确定循环的开始的位置)。

然后分别讨论几种情况:

设right表示第一次放雷达的位置(最左端的岛屿,为了能够最大覆盖,需要从maxx开始放置)。

假设下一个岛屿的索引是i+1(起始位置从i+1开始):

  • 如果points[i+1].mixx > right 很显然I(i+1)是放置在right雷达覆盖不了的,所以需要增加雷达的数量,同时把雷达放在points[i+1].maxx上,(图1-1)。
  • 很显然,如果points[i+1] <=tight 那么right位置的雷达是可以覆盖的,那我不管他(图1-1)。

  • 如果points[i+1].mixx <=right 且points[i+1].maxx < right。也就是图1-2的情况,算法只要将雷达重新放在points[i+1].maxx上。就okay。

3.附上代码(但是无法AC。郁闷)

#include "stdio.h"
#include "stdlib.h"
#include <cmath>
#define N 1001
#include <algorithm>
struct point {
	int x; int y;
	int minx; int maxx;

};
point points[N];
//POJ 1328
//贪心算法 我认为是可以的 但是还是不行 奇怪了 
int res[N];
int np, d;
bool cmp(const point &l, const point &p)
{
	return l.minx < p.minx;
}
bool set_min_xpoint(point *dest)
{
	int mm, mmmax;
	bool flag = false;
	if (dest->y > d)
	{
		flag = true;
	}
	else
	{
		int sr = sqrt(d*d-dest->y *dest->y);
		dest->minx = dest->x- sr;
		dest->maxx = dest->x+ sr;
		flag = false;
	}
	return flag == false;
}
int main()
{
	int pos = 0;
	while (~scanf("%d %d", &np, &d) && (np != 0 && d != 0))
	{
		bool res1 = true;
		for (int i = 0; i<np; ++i)
		{
			scanf("%d %d", &points[i].x, &points[i].y);
			if (!set_min_xpoint(&points[i]))
			{
				res1 = false;
				continue;
			}
			//printf("---%d %d\n", points[i].minx, points[i].maxx);
		}
		if (res1 == false)
		{
			printf("Case %d: %d\n", ++pos, -1);
			continue;
		}
		std::sort(points, points + np, cmp);
		/*
		int sum = 1;
		for (int i = 0; i < np - 1; ++i)
		{
			if (points[i + 1].minx >= points[i].minx && points[i + 1].minx <= points[i].maxx)
			{
				--sum;
			}
		}
		*/
		//选取之前放置雷达的位置 然后查找下一个的左端点是否在当前的右边界的:1.右边:那么在当前位置的右边放下雷达
		//2.左边:那么肯定是可以覆盖的
		//如果下一个的位置的右边界在之前放置雷达的位置左边  那么就要在这个的最大位置放置雷达 那么之前的都可以覆盖了
		//如果在右边也在覆盖范围内
		int sum = 1;
		int right = points[0].maxx;
		for (int i = 0; i < np - 1; ++i)
		{
			if (points[i + 1].minx > right)
			{
				++sum;
				right = points[i + 1].maxx;
			}
			else if(points[i+1].maxx < right)
			{
				right = points[i + 1].maxx;
			}
		}
		//*/
		
		printf("Case %d: %d\n", ++pos, sum);
	}

	return 0;
}