【第35题】二分查找，哎，不提了[NOIP2015 提高组] 跳石头

#include <bits/stdc++.h>
using namespace std;
#define endl '\n';

void best_coder() {
    int n, m, l;
    scanf("%d%d%d", &l, &n, &m);
    vector<int> v(n + 2);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &v[i]);
    }
    v[n + 1] = l;
    int x = 1, y = l;
    int mid;
    int ans;
    while (x <= y) {
        int cnt = 0;
        int now = 0;
        mid = (x + y) >> 1;
        for (int i = 1; i <= n + 1; ++i) {
            if (v[i] - v[now] < mid) {
                ++cnt;
            } else {
                now = i;
            }
        }
        if (cnt <= m) {
            x = mid + 1;
            ans = mid;
        } else {
            y = mid - 1;
        }
    }
    printf("%d", ans);
}

void happy_coder() {

}

int main() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 小码匠
    best_coder();

    // 最优解
    // happy_coder();

    // 返回
    return 0;
}