二分答案跳石头游戏

步骤：

输入：用户输入了三个整数，分别表示石头的总长度l，石头的数量n，以及最多可以撤去的石头数量m。
初始化石头位置数组：创建一个长度为n+2的数组arr，用于存储每块石头的位置。数组的第一项和最后一项分别表示起点和终点的位置，因此初始化为0和l。
计算最小相邻石头间距：循环读入每块石头的位置，并计算出最小的相邻石头间距，存储在变量longmin中。
二分查找：初始化二分查找的左右边界，左边界为最小相邻石头间距，右边界为总长度l。在二分查找的过程中，通过调用check函数来判断当前的最大跳跃长度是否满足条件。
判断函数check： check函数用于判断在给定的最大跳跃长度下是否可以跳过最多可以撤去的石头数量。在每次跳跃时，遍历石头数组，根据当前位置和上一次跳跃位置计算跳跃距离，如果距离大于等于最大跳跃长度，则更新当前位置；否则，说明无法跳过这块石头，撤去数量加一。最后比较撤去数量是否超过了允许的最大值m，如果超过则返回0，否则返回1。
输出结果：输出最终的最大跳跃长度。

#include<iostream>
using namespace std;

// 全局变量，分别表示石头的总长度l，石头的数量n，以及最多可以撤去的石头数量
int n, max_removed_stones, l;

// 函数check用于判断是否可以在最大跳跃长度为x的情况下跳过最多可以撤去的石头数量
int check(int x, int arr[]) {
    int now = 0; // 当前所在位置
    int removed_stones = 0; // 记录已经撤去的石头数量
    for(int i = 1; i <= n + 1; i++) {
        if(arr[i] - arr[now] >= x) // 如果当前位置与上一次跳跃位置之间的距离大于等于x
            now = i; // 更新当前位置为跳跃位置
        else 
            removed_stones++; // 否则，说明无法跳过这块石头，撤去数量加一
    }
    if(removed_stones > max_removed_stones) // 如果撤去的石头数量超过了允许的最大值
        return 0; // 返回0，表示无法跳过这么多石头
    else 
        return 1; // 否则返回1，表示可以跳过这么多石头
}

int main() {
    // 输入石头的总长度l，石头的数量n，以及最多可以撤去的石头数量max_removed_stones
    cin >> l >> n >> max_removed_stones; 

    // 创建一个长度为n+2的数组，用于存储每块石头的位置
    int arr[n + 2]; 
    arr[0] = 0; // 第一块石头位置为0
    arr[n + 1] = l; // 最后一块石头位置为总长度l

    // 初始化最小跳跃长度为一个较大的值，这里使用1左移10位来表示2^10
    int longmin = 1 << 10; 

    // 循环读入每块石头的位置，并计算出最小的相邻石头间距
    for(int i = 1; i <= n; i++) {
        cin >> arr[i];
        longmin = min(longmin, arr[i] - arr[i - 1]);
    }
    
    int left = longmin, right = l; // 初始化二分查找的左右边界
    int mid; // 定义中间位置
    int max_jump_distance; // 记录最终的最大跳跃长度

    // 二分查找，直到左右边界重合
    while(left <= right) {
        mid = (left + right) / 2; // 计算中间位置
        if(check(mid, arr) == 1) { // 如果当前中间位置的跳跃长度满足条件
            left = mid + 1; // 缩小左边界，并记录当前的最大跳跃长度
            max_jump_distance = mid;
        } else {
            right = mid - 1; // 否则，缩小右边界
        }
    }

    // 输出最终结果，即最大跳跃长度
    cout << max_jump_distance << endl; 
    return 0;
}

有个二分答案的算法，大部分时间复杂度为O(nlogn)。

二分答案（Binary Search for Answer）是一种常见的搜索技巧，通常用于解决满足某种条件的最优解问题。该技巧通常适用于满足以下两个条件的问题：