题解：P2678 [NOIP2015 提高组] 跳石头

GSQ0829 · 2024-12-31 17:53:15 · 题解

题目传送门

思路：

这题很明显，就是二分题，要求最短跳跃距离的最大值。

那么，首先我们要先知道二分的模版。

while (l < r) {
    mid = (l + r + 1) / 2;
    if (check(mid)) l = mid;
    else r = mid - 1;
}

在知道了模版之后，我们就要来写判断函数了。

我们会发现如果两个点之间距离小于最小跳跃距离， 那么就必须将其中一个石头移去。

所以根据这个，我们就可以写出判断函数了。

bool check(int d) {
    int p = 0, ans = 0;
    for (int i = 1; i <= n; i++) {
        if (stone[i] - p < d) ans++;
        else p = stone[i];
    }
    if (ans <= m) return true;
    else return false;
}

最后，将两者结合，就是最终代码了。

code：

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 50001;
int stone[MAXN], a, n, m;

bool check(int d) {
    int p = 0, ans = 0;
    for (int i = 1; i <= n; i++) {
        if (stone[i] - p < d) ans++;
        else p = stone[i];
    }
    if (ans <= m) return true;
    else return false;
}

int main() {
    scanf("%d %d %d", &a, &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &stone[i]);
    stone[++n] = a;
    int l = 0, r = a, mid;
    while (l < r) {
        mid = (l + r + 1) / 2;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    printf("%d\n", l);
    return 0;
}