代码语言：javascript复制
#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("%dn", ans);
}
int main()
{
scanf("%d %d", &N, &R);
for (int i = 0; i < N; i)
{
scanf("%d", &x[i]);
}
solve();
return 0;
}
