给出代码用c++的区间完成这道题华罗庚大道在国庆时准备举办庆祝活动,为了确保活动的顺利举行,AA市的相关部门要在该条道路上设置安保人员。 该大道可以看作一条坐标从 00 到 1000010000 的线段,该线段上有 nn 个点可以设置安保人员,每个点的安保人员负责安保的范围是为区域半径为 rr 的区间,也就是说,位于坐标值为 xx 的位置的安保人员,将会负责 [x-r,x+r][x−r,x+r] 的区域。 请问,这 nn 个点至少要选择几个点设置安保人员,才能使得整条大道的所有位置都有安保人员负责?
时间: 2024-02-15 21:05:42 浏览: 99
以下是完整的代码实现:
```c++
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 10005;
int n, r, x[N];
int main()
{
cin >> n >> r;
for (int i = 1; i <= n; i++) {
cin >> x[i];
}
sort(x + 1, x + n + 1); // 排序
int ans = 0, pos = 1;
while (pos <= n) {
int cur = pos;
while (cur <= n && x[cur] - x[pos] <= r) {
cur++;
}
if (cur > n) {
ans++;
break;
}
int nxt = cur;
while (nxt <= n && x[nxt] - x[cur] <= r) {
nxt++;
}
ans++;
pos = nxt - 1;
}
cout << ans << endl;
return 0;
}
```
输入格式:
第一行包含两个整数 n 和 r。
第二行包含 n 个整数表示每个点的位置。
输出格式:
输出一个整数表示至少需要选择的点的个数。
阅读全文