首页 > 代码库 > 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(); }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。