C++C++# NOIP2015 提高组 跳石头## 题目背景一年一度的跳石头比赛又要开始了!## 题目描述这项比赛将在一条笔直的河道中进行河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间有 $N$ 块岩石不含起点和终点的岩石。在比赛过程中选手们将从起点出发每一步跳向相邻的岩石直至到达终点。为了提高比赛难度组委会计划移走一些岩石使得选手们在比赛过程中的最短跳

#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;
}
``