1 条题解
-
0
#include<bits/stdc++.h> using namespace std; int arr[1010]; // 存储可设置安保人员的坐标 int main(){ int n,r; cin >> n >> r; // [1] 输入可设置点的数量n和安保人员负责的半径r for(int i = 0; i < n; i++) cin >> arr[i]; // [2] 输入所有可设置点的坐标 sort(arr, arr + n); // [3] 对坐标进行升序排序,便于贪心选择 int w = 0; // 当前已覆盖到的最右端位置,初始为0(道路起点) int sum = 0; // 记录已选择的安保人员数量 // [4] 贪心选择覆盖点:遍历所有坐标,直到覆盖整条道路(w >= 10000) for(int i = 0; i < n && w < 10000; i++){ // 条件:当前点的左边界能覆盖到当前已覆盖的最右端,且下一个点的左边界无法覆盖 // 说明当前点是能延伸最远的最优选择 if(i < n-1 && arr[i] - r <= w && arr[i+1] - r > w){ sum++; // 选择当前点 w = arr[i] + r; // 更新已覆盖的最右端为当前点的右边界 } // 处理最后一个点:如果它的左边界能覆盖当前已覆盖的最右端,且道路还没被完全覆盖 if(i == n-1 && arr[i] - r <= w){ sum++; w = arr[i] + r; } } cout << sum; // [5] 输出最少需要选择的安保人员数量 return 0; }
- 1
信息
- ID
- 1041
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 2
- 标签
- 递交数
- 2
- 已通过
- 1
- 上传者