站岗

题目

我是一个保安，爱吃小熊饼干。

小J和小R在去一教上课的路上发现长桥上正在安装电子摄像头作为电子保安！

每两个电子摄像头之间都有一定的距离，这其中距离最大的值被小R叫做长桥的不安全指数。

小R发现现在已经安好了一些监控，还有一些需要安装，他想知道如果所有电子摄像头都完成安装后长桥的不安全指数最小会是多少。

但小R现在急着去上课，小J看起来又不是很靠谱，于是这个问题被交给了你！

长桥上已经安装好了一些电子摄像头，现在还有一些摄像头需要安装，小J和小R想知道在所有摄像头都安装完毕后长桥的最小不安全指数会是多少，数据保证长桥起点和终点已经有了路标，同时长桥长度为整数，所有摄像头距离起点都必须是整数个单位距离。

输入：第1行包括三个数 L,N,K，分别表示长桥的长度，原有电子摄像头的数量，以及最多可增设的电子摄像头数量。第2行包括递增排列的 N 个整数，分别表示原有的 N 个电子摄像头的位置。电子摄像头的位置用距起点的距离表示，且一定位于区间 [0,L] 内。
输出：输出一个整数，表示长桥的最小不安全指数。

样例1：

101 2 1
0 101

51

样例2：

200 5 5
0 45 90 150 200

25

提示：对于 30% 的数据，保证 L 在 int 范围内，2≤N≤100，0≤K≤100。对于 60% 的数据，保证 L 在 int 范围内，2≤N≤1000，0≤K≤1000。对于 100% 的数据，保证 L 在 int 范围内，2≤N≤100000，0≤K≤100000。

思路

对"最小不安全指数"做二分答案。设候选答案为 mid，验证它是否可行：遍历所有相邻摄像头间距 gap，若 gap > mid，则这段需要插入 ceil(gap/mid) - 1 个摄像头（上取整用 (gap + mid - 1) / mid 实现），累加所有间距的需求量，若总数 ≤ K 则 mid 可行。二分范围取 [1, 现有最大间距]，每次找到可行的 mid 就收缩右边界，最终得到最小可行值。

#include<bits/stdc++.h>
using namespace std;

bool canAchieve(int d, const vector<int>& pos, int K) {
    int needed = 0;
    for (int c=0;c<pos.size()-1;++c) {
        int gap = pos[c+1] - pos[c];
        if (gap>d) {
            // 需要在这段中间加摄像头
            needed+=(gap+d-1)/d-1; // ceil(gap/d)-1
            if (needed>K) return false;
        }
    }
    return needed <= K;
}

int main() {
    int L, N, K;
    cin >> L >> N >> K;
    vector<int> pos(N);
    for (int i = 0; i < N; ++i) {
        cin >> pos[i];
    }

    // 找最大间隔作为右边界
    int max_gap = 0;
    for (int i = 0; i < N - 1; ++i) {
        max_gap=max(max_gap,pos[i+1]-pos[i]);
    }

    int left=1,right=max_gap,ans=max_gap;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (canAchieve(mid, pos, K)) {
            ans = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    cout << ans << endl;
    return 0;
}

复杂度分析

• 时间复杂度：O(N log L)，二分 O(log L) 次，每次验证遍历 N 个间距。
• 空间复杂度：O(N)，存储摄像头位置数组。

← 返回菜鸟的coding