跳石头（二分）

题目分析

在一条笔直的河道中，起点和终点之间有 N 块岩石。组委会至多移走 M 块岩石（起点和终点不能移走），要求使得选手在比赛过程中最短跳跃距离尽可能大。需要求出这个最短跳跃距离的最大值。

解题思路

这是一个典型的最大化最小值问题，通常使用二分答案法求解。具体思路如下：

1. 二分答案：假设最短跳跃距离为 ，检查是否能在移走不超过 块岩石的情况下，使得所有相邻跳跃（包括起点到第一块岩石、岩石之间、最后一块岩石到终点）的距离都不小于 。
2. 检查函数（check 函数）：
   • 从起点（位置 0）开始，遍历所有岩石（包括终点）。
   • 维护上一个落脚点的位置（初始为起点）。
   • 对于当前岩石，如果它与上一个落脚点的距离小于 ，则移走该岩石（计数增加）。
   • 否则，将该岩石作为新的落脚点。
   • 最后检查终点与最后一个落脚点的距离是否不小于 。
   • 如果移走的岩石数量不超过 且最后一段距离满足条件，则 可行。
3. 二分搜索：
   • 左边界 （最小可能距离），右边界 （最大可能距离）。
   • 当 时，取 （避免死循环）。
   • 如果 为真，则 （尝试更大的距离）；否则 。
   • 最终 即为答案。

复杂度分析

• 时间复杂度：二分搜索 ，每次检查 ，总复杂度 。
• 空间复杂度： 存储岩石位置。

代码实现

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

bool check(int x, vector<int>& rocks, int N, int M, int L) {
    int count = 0; // 记录移走的岩石数量
    int last = 0;  // 上一个落脚点的索引（起点索引为0）
    // 遍历中间岩石（索引1到N）
    for (int i = 1; i <= N; i++) {
        if (rocks[i] - rocks[last] < x) {
            count++; // 移走当前岩石
            if (count > M) { // 提前终止：移走数量超过M
                return false;
            }
        } else {
            last = i; // 保留当前岩石，更新落脚点
        }
    }
    // 检查最后一段（最后一个落脚点到终点）
    if (L - rocks[last] < x) {
        return false;
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int L, N, M;
    cin >> L >> N >> M;
    vector<int> rocks(N + 2);
    rocks[0] = 0; // 起点
    for (int i = 1; i <= N; i++) {
        cin >> rocks[i];
    }
    rocks[N + 1] = L; // 终点

    int left = 1, right = L;
    while (left < right) {
        int mid = (left + right + 1) / 2;
        if (check(mid, rocks, N, M, L)) {
            left = mid;
        } else {
            right = mid - 1;
        }
    }
    cout << left << endl;
    return 0;
}