一、题目内容
POJ 3069 原题地址
二、题意解释
一个直线上有N个点。点i的距离是Xi。从这些点中选取若干个加上标记。
要求:对于每个点,与其距离为R的范围内必有做标记的点(包括自身)。求至少标记多少点才能满足要求。
三、代码及注释
#include<stdio.h>
#include<algorithm>
using namespace std
;
int X
[1001];
int main(){
int n
,r
;
while(scanf("%d%d",&r
,&n
)!=EOF){
if(r
==-1&&n
==-1) break;
for(int i
=0;i
<n
;i
++){
scanf("%d",&X
[i
]);
}
sort(X
,X
+n
);
int ans
=0;
int i
=0;
while(i
<n
){
int s
=X
[i
++];
while(i
<n
&&X
[i
]<=s
+r
) i
++;
int p
=X
[i
-1];
while(i
<n
&&X
[i
]<=p
+r
) i
++;
ans
++;
}
printf("%d\n",ans
);
}
return 0;
}
转载请注明原文地址:https://blackberry.8miu.com/read-1585.html