Saruman's Army

#include <iostream>
#include <algorithm>
using namespace std;
/*直线上有N个点。点i的位置是Xi。从这N个点中选择若干个，给它们加上标记。
对每一个点，其距离为R以内的区域里必须有带有标记的点
(自己本身带有标记的点，可以认为与其距离为0的地方有一个带有标记的点)。 
在满足这个条件的情况下，希望能为尽可能少的点添加标记。请问至少要有多少点被加上标记?
限制条件：
1 ≤N ≤1000
0 ≤R ≤1000
0 ≤Xi ≤1000

输入								输出 
N=6								3
R=10
X={1, 7, 15, 20, 30, 50} 
*/ 
const int MAX_N = 1001;
int N, R;
int x[MAX_N];

void solve()
{
	sort(x, x + N);
	int i = 0, ans = 0;
	while (i < N)
	{
		// s是没有被覆盖的最左的点的位置 
		int s = x[i++];
		// 一直向右前进直到s的距离大于R的点 
		while (i < N && x[i] <= s + R)	++i;
		// p是新加上标记的点的位置 
		int p = x[i - 1];
		++ans;
		// 一直向右前进知道距p的距离大于R的点 
		while (i < N && x[i] <= p + R)	++i;
	}
	printf("%d\n", ans);
}

int main()
{
	scanf("%d %d", &N, &R);
	for (int i = 0; i < N; ++i)
	{
		scanf("%d", &x[i]);
	}
	solve();
	return 0;
}