[NOIP2015 提高组] 跳石头

题目背景

一年一度的“跳石头”比赛又要开始了!

题目描述

这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有 $N$ 块岩石（不含起点和终点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。

为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走 $M$ 块岩石（不能移走起点和终点的岩石）。

输入格式

第一行包含三个整数 $L,N,M$，分别表示起点到终点的距离，起点和终点之间的岩石数，以及组委会至多移走的岩石数。保证 $L \geq 1$ 且 $N \geq M \geq 0$。

接下来 $N$ 行，每行一个整数，第 $i$ 行的整数 $D_i( 0 < D_i < L)$，表示第 $i$ 块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出，且不会有两个岩石出现在同一个位置。

输出格式

一个整数，即最短跳跃距离的最大值。

样例 #1

样例输入 #1

样例输出 #1

提示

输入输出样例 1 说明

将与起点距离为 $2$和 $14$ 的两个岩石移走后,最短的跳跃距离为 $4$(从与起点距离 $17$ 的岩石跳到距离 $21$ 的岩石,或者从距离 $21$ 的岩石跳到终点)。

数据规模与约定

对于 $20%$的数据，$0 \le M \le N \le 10$。
对于 $50%$ 的数据，$0 \le M \le N \le 100$。
对于 $100%$的数据，$0 \le M \le N \le 50000,1 \le L \le 10^9$。

讲解一下这道题内容：这道题是一个经典的二分搜索问题。我们需要找到一个最短跳跃距离的最大值，也就是说，我们需要找到一个跳跃距离，在移走至多 $M$ 块岩石的情况下，选手们能够跳到终点。

首先，我们可以观察到，如果选手们能够跳至少 $d$ 的距离，那么他们也能够跳过任意小于 $d$ 的距离。因此，我们可以使用二分搜索的方法来找到最短跳跃距离的最大值。

我们可以设定一个最小跳跃距离的下界为 $0$，一个最大跳跃距离的上界为 $L$。然后，我们可以在这个范围内进行二分搜索，不断缩小跳跃距离的范围，直到找到一个合适的跳跃距离。

在每一次二分搜索中，我们可以假设当前的跳跃距离为 $mid$，然后计算在移走至多 $M$ 块岩石的情况下，选手们能否跳到终点。为了计算这个跳跃距离是否可行，我们可以使用贪心的思想。

我们可以从起点开始，依次检查每一块岩石，看它是否能够被跳过。如果当前岩石与上一个岩石的距离小于等于 $mid$，则可以将这块岩石移走。移走一块岩石相当于将当前的跳跃距离延长了 $1$，同时将已移走的岩石数 $M$ 减少 $1$。在移走一块岩石后，我们需要更新上一个岩石的位置，并继续检查下一块岩石。

如果在检查完所有的岩石之后，选手们能够跳到终点，那么说明当前的跳跃距离是可行的。我们可以继续在跳跃距离更大的范围内进行搜索，直到找到一个不可行的跳跃距离为止。此时，最短跳跃距离的最大值就是这个不可行的跳跃距离减去 $1$。

接下来，我们可以详细讲解一下代码的实现。

首先，我们可以读入输入的三个整数 $L, N, M$，以及岩石的位置数组 $D$。

然后，我们可以定义一个函数 $check$，用来判断给定的跳跃距离是否可行。在函数中，我们需要维护一个变量 $cnt$，表示已经移走的岩石数。初始时，$cnt$ 的值为 $0$。

接下来，我们可以使用一个循环来依次检查每一块岩石。在循环中，我们首先需要判断当前岩石与上一个岩石的距离是否小于等于给定的跳跃距离。如果小于等于，则可以将当前岩石移走，同时将 $cnt$ 的值加 $1$。然后，我们需要更新上一个岩石的位置。

在检查完所有的岩石之后，我们需要判断选手们是否能够跳到终点。如果 $cnt \le M$，则说明选手们能够跳到终点，返回 $true$；否则，返回 $false$。

接下来，我们可以使用二分搜索的方法来找到最短跳跃距离的最大值。我们可以设定一个最小跳跃距离的下界为 $0$，一个最大跳跃距离的上界为 $L$。然后，我们可以在这个范围内进行二分搜索。

在每一次二分搜索中，我们可以假设当前的跳跃距离为 $mid$。然后，我们可以调用 $check$ 函数来判断给定的跳跃距离是否可行。

如果 $check(mid)$ 返回 $true$，则说明当前的跳跃距离是可行的，我们可以继续在跳跃距离更大的范围内进行搜索，将最小跳跃距离的下界更新为 $mid+1$。

如果 $check(mid)$ 返回 $false$，则说明当前的跳跃距离是不可行的，我们需要将最大跳跃距离的上界更新为 $mid-1$。

在二分搜索结束后，我们可以返回最大跳跃距离的上界作为最短跳跃距离的最大值。我们可以将这个值减去 $1$，得到最终的答案。

下面是代码的实现：

#include <iostream>
#include <vector>
using namespace std;

bool check(int mid, int M, vector<int>& D) {
    int cnt = 0;
    int prev = 0;
    for (int i = 0; i < D.size(); i++) {
        if (D[i] - prev <= mid) {
            cnt++;
        } else {
            prev = D[i];
        }
    }
    return cnt <= M;
}

int main() {
    int L, N, M;
    cin >> L >> N >> M;
    vector<int> D(N);
    for (int i = 0; i < N; i++) {
        cin >> D[i];
    }

    int left = 0;
    int right = L;
    int ans = 0;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (check(mid, M, D)) {
            ans = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    cout << ans - 1 << endl;

    return 0;
}

该实现的时间复杂度为 $O(N \log L)$，其中 $N$ 是岩石的数量，$L$ 是起点到终点的距离。由于题目中给出的数据规模比较小，所以这个复杂度是可以接受的。

希望可以帮助到你！

NOIP2015 提高组 - 跳石头：二分搜索算法求解最短跳跃距离最大值