题目描述
华罗庚大道在国庆时准备举办庆祝活动,为了确保活动的顺利举行,A市的相关部门要在该条道路上设置安保人员。
该大道可以看作一条坐标从 0 到 10000 的线段,该线段上有 n 个点可以设置安保人员,每个点的安保人员负责安保的范围是为区域半径为 r 的区间,也就是说,位于坐标值为 x的位置的安保人员,将会负责 [x−r,x+r] 的区域。
请问,这 n 个点至少要选择几个点设置安保人员,才能使得整条大道的所有位置都有安保人员负责?
输入
第一行两个整数 n 和 r(n≤1000,r≤20000)。分别表示可设置安保人员的位置数量和安保人员可以负责的区域半径。
第二行 n 个数,分别表示可设置安保人员的点的坐标。
输出
一个数,表示最少需要选择设置安保人员的位置数量。(本题测试数据确保有解)
样例
输入
5 4000
0 1000 3000 2000 9000
输出
2
用贪心或区间如何做
#include<bits/stdc++.h>
using namespace std;
int n,r,a[100010];
int main(){
cin>>n>>r;
for(int i=1;i<=n;i++){
cin>>a[i];
}
return 0;
}
//后面不会了