python/TangDou/XiTi/1310.cpp

#include <bits/stdc++.h>

using namespace std;
int a[1001] = {0};
int L, n, m;

//在以mid为最短的跳跃距离时，有多少块岩石符合要求
int judge(int mid) {
    int cnt = 0, k = 0; //k为探测是否需要移除的点
    for (int i = 1; i <= n; i++) {
        if (a[i] - k <= mid) {
            cnt++;
        } else {
            k = a[i];
        }
    }
    return cnt;
}


int main() {
    //输入+输出重定向
    freopen("../1310.txt", "r", stdin);

    cin >> L >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    //最后的收尾岩石
    n++;
    a[n] = L;

    //二分法的起始值
    int l = 0, r = L;

    //二分法的模板
    while (l <= r) {
        int mid = (l + r) / 2;
        //如果使用这个mid，那么需要移除多少个岩石
        int x = judge(mid);
        //如果大于m, 表示意味着mid取大了，需要缩减
        if (x > m) {
            r = mid - 1;
        } else { //mid值取小了，需要增大
            l = mid + 1;
        }
    }
    //l最终是结果
    cout << l << endl;
    //关闭文件
    fclose(stdin);
    return 0;
}