题目链接

River Hopscotch POJ - 3258

思路

$$ 假设一个可行接然后验证,注意二分上界！ $$

时间复杂度

$$ O(NlogN) $$

代码

#include <cstdio>
#include <algorithm>

using namespace std;

const int MAXN = 5e4 + 10;
int L, N, M;
int a[MAXN];

bool check(int mid) {
    int cnt = 0;
    int cur = 0;
    for (int i = 1; i <= N; i++) {
        if (a[i] - cur < mid || L - a[i] < mid) {
            cnt++;
        } else {
            cur = a[i];
        }
    }
    return cnt <= M;
}

int main() {    
    scanf("%d%d%d", &L, &N, &M);// don't forget &
    for (int i = 1; i <= N; i++) {
        scanf("%d", &a[i]);// don't forget &
    }
    sort(a + 1, a + 1 + N);
    int l = 1, r = L, ans = 1;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (check(mid)) {
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    printf("%d", ans);
    return 0;
}