C++: [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

25 5 2 
2
11
14
17 
21

样例输出 #1

4

提示

输入输出样例 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$。

代码实现

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 判断移除最短距离为d的岩石后，是否能够满足最短跳跃距离大于等于k
bool canRemove(vector<int>& rocks, int d, int k, int m) {
    int cnt = 0; // 记录已移除的岩石数量
    int last = 0; // 记录上一个岩石的位置
    for (int i = 0; i < rocks.size(); i++) {
        if (rocks[i] - last < d) {
            cnt++; // 移除当前岩石
        } else {
            last = rocks[i]; // 更新上一个岩石的位置
        }
    }
    // 判断移除的岩石数量是否超过了m，并且最后一个岩石到终点的距离是否小于d
    return cnt <= m && rocks.back() - last >= d;
}

int main() {
    int L, N, M;
    cin >> L >> N >> M;
    
    vector<int> rocks(N);
    for (int i = 0; i < N; i++) {
        cin >> rocks[i];
    }
    
    sort(rocks.begin(), rocks.end()); // 将岩石按照与起点的距离从小到大排序
    
    int left = 1; // 最短跳跃距离的最小值
    int right = L; // 最短跳跃距离的最大值
    
    while (left < right) {
        int mid = (left + right + 1) / 2; // 二分查找的中间值
        if (canRemove(rocks, mid, L, M)) {
            left = mid; // 可以满足条件，更新最小值
        } else {
            right = mid - 1; // 不满足条件，更新最大值
        }
    }
    
    cout << left << endl;
    
    return 0;
}

总结

本篇博客讲解了 NOIP2015 提高组 跳石头问题的解题思路和代码实现，使用二分算法来求解最短跳跃距离的最大值。二分算法是一种高效的算法，可以帮助我们快速找到最优解。在解决类似问题时，可以考虑使用二分算法来提高效率。

希望这篇文章对你有帮助！