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

这道题可以使用二分查找的方法来解决。

首先，我们需要找到最短跳跃距离的最大值，即使得选手们在比赛过程中的最短跳跃距离尽可能长。

我们可以将问题转化为判断是否存在一种移除岩石的方案，使得选手们在比赛过程中的最短跳跃距离大于等于某个给定的值。

具体的做法如下：

1. 将所有岩石的位置保存在一个数组中，并按照与起点的距离从小到大排序。

2. 使用二分查找确定最短跳跃距离的最大值。

   • 设定最小跳跃距离的初始值为1，最大跳跃距离的初始值为L-1。

   • 在每一次二分查找中，假设中间值为mid，即最短跳跃距离的候选值。

   • 对于每一个岩石，从当前岩石开始，向后遍历，计算距离下一个岩石的距离，如果距离小于等于mid，则移除当前岩石。

   • 如果移除的岩石数小于等于M，则说明存在一种移除岩石的方案，使得最短跳跃距离大于等于mid。

   • 如果移除的岩石数大于M，则说明不存在一种移除岩石的方案，使得最短跳跃距离大于等于mid。

   • 根据二分查找的性质，不断更新最小跳跃距离或最大跳跃距离，直到最小跳跃距离大于最大跳跃距离为止。

3. 输出最小跳跃距离的最大值。

时间复杂度分析：

• 排序所有岩石的位置需要O(NlogN)的时间。

• 对于每一次二分查找，需要遍历所有岩石，计算移除岩石的数量，时间复杂度为O(N)。

• 二分查找的次数最多为log(L)次。

因此，总的时间复杂度为O(NlogN*log(L))。

代码实现如下：

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

bool canRemoveStones(vector<int>& stones, int L, int N, int M, int minDist) {
    int removeCount = 0;
    
    for (int i = 0; i < N; i++) {
        int j = i + 1;
        while (j < N && stones[j] - stones[i] <= minDist) {
            j++;
        }
        
        removeCount += j - i - 1;
        i = j - 1;
    }
    
    return removeCount <= M;
}

int main() {
    int L, N, M;
    cin >> L >> N >> M;
    
    vector<int> stones(N);
    for (int i = 0; i < N; i++) {
        cin >> stones[i];
    }
    
    int left = 1, right = L - 1;
    int ans = 0;
    
    while (left <= right) {
        int mid = (left + right) / 2;
        
        if (canRemoveStones(stones, L, N, M, mid)) {
            ans = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    cout << ans << endl;
    
    return 0;
}

时间复杂度：O(NlogN*log(L))