P2678_跳石头

解题思路

弱弱的写一个二分答案
可以通过二分的思想，判断该 mid 是否可以作为最小距离的最大值，如果可以便更新左边界（最小值最大化）。
那么如何判断是否可以作为最小距离的最大值呢？
这里有一点贪心的思想，可以判断当前点距离上一个点的距离是否大于等于 mid，如果不满足便拿掉该块石头，如果拿掉的石头数量超过 m 个，也说明该 mid 不满足。

code

#include<iostream>
#include<cstdio>
using namespace std;
#define MAXN 50005

int arr[MAXN];
int e, n, m;

int check(int x) {
    int last = 0, now, cnt = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] - last < x) {
            if (i == n - 1 || cnt == m) return 0;
            cnt += 1;
        } else {
            last = arr[i];
        }
    }
    return 1;
}

int solve() {
    int l = 0, r = e, mid;
    while (l < r) {
        mid = (l + r + 1) >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return r;
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> e >> n >> m;
    for (int i = 0; i < n; i++) cin >> arr[i];
    arr[n++] = e;
    cout << solve() << endl;
    return 0;
}