跳石头

#include <bits/stdc++.h>
using namespace std;
int li[50010];
int L, n, k;
bool check(int mn) {
    int now = 1;
    int know = 0;
    while (now != n) {
        if (mn == 2) {
            printf("/%d %d/\n", now, know);
        }
        int offset = 1;
        while (now + offset <= n && li[now + offset] - li[now] < mn) {
            offset++;
            know++;
        }
        now += offset;
        if (now > n)
            return 0;
    }
    // printf("/%d %d/\n", mn, know);
    if (know <= k)
        return 1;
    else
        return 0;
}
int main() {
    cin >> L >> n >> k;
    li[1] = 0;
    for (int i = 1; i <= n; i++) {
        cin >> li[i + 1];
    }
    n += 2;
    li[n] = L;
    int l = 0;
    int r = L;
    int ans = 0;
    while (l <= r) {
        int mid = (l + r) >> 1;
        printf("/%d/", mid);
        if (check(mid)) {
            l = mid + 1;
            ans = max(ans, mid);
        } else
            r = mid - 1;
        // printf("/%d %d/\n", l, r);
    }
    cout << ans;
}
// 0 2 4 7 8

点赞

发表回复