1 条题解

  • 0
    @ 2026-2-1 16:00:59
    #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
    上传者