首页 > 代码库 > poj3069Saruman's Army

poj3069Saruman's Army

题意大概是这样,给你一堆数,每个数代表一个点的位置,可以理解成在一个
一维坐标里的一些点,每个点都有一个数字代表。
还给了你一个数代表半径。
给你一个规则,当你选择某个点标记的时候,以它为中心,半径所能扫到的区域
内,所有点都会被标记。
现在要把所有点标记,问你最少选择几次就能够标记完。
我的做法是贪心,从最左边开始,数一个点出来,这个点刚好超过以最左边那个点
为中心能够扫到的区域,然后再以这个点为中心,再数一个点出来,这个点刚好
超过以这个为中心的点所能扫到的区域,这个时候选择标记这个为中心的点,以此类推,
当扫到最后一个点的时候,此时选择标记的点的数目就是最小数目。
我的AC代码如下:

#include<cstdio>
#include<algorithm>
using namespace std;
int r,num,dot[1010];
bool cmp(int a,int b)
{
	return a<b;
}
bool init()
{
	int i;
	scanf("%d%d",&r,&num);
	if(r==num&&r==-1)
		return 0;
	for(i=0;i<num;i++)
		scanf("%d",&dot[i]);
	sort(dot,dot+num,cmp);
	return 1;
}
void result()
{
	int i,sum=0,s=0;
	while(s<num)
	{
		for(i=s;i<num&&dot[i]<=dot[s]+r;i++);
		s=i-1;
		for(i=s;i<num&&dot[i]<=dot[s]+r;i++);
		s=i;
		sum++;
	}
	printf("%d\n",sum);
}
int main()
{
	while(init())
		result();
}