要求数轴上任何一个点的R范围内都要存在一个以上被标记得点,求点的最少数量。
#include<stdio.h>
#include<algorithm>
using namespace std;
int n,m,r;
int x[1000];//每个点的位置
int main()
{
int ans=0; int i; int s,t;
scanf("%d%d",&n,&r);//n点的数量 r要求的半径
for(i=0;i<n;i++)
scanf("%d",&x[i]);
sort(x,x+n);//先让它升序
i=0;
while(i<n)
{
s=x[i++];
while(i<n&&x[i]<=s+r) i++;//先找到第一个点范围外的点
t=x[i-1];//被标记的点的位置
while(i<n&&x[i]<=t+r) i++;//让i跳到被标记点的范围外,再进行下一次循环
ans++;
}
printf("%d",ans);
}