洛谷-P2678 [NOIP 2015 提高组] 跳石头 题解

题目链接：https://www.luogu.com.cn/problem/P2678

题目大意

在一条长度为 L的河道中，起点位于位置 0，终点位于位置 L。中间有 N 块岩石，位置已知且按升序给出。现在最多可以移走 M 块岩石（不能动起点和终点），目标是使得选手在跳跃过程中所有相邻两步之间的最短距离尽可能大。

输出这个最大可能的最短跳跃距离。

解题思路

1. 转化问题：最大化最小值 → 二分答案

这是一个典型的 “最大化最小值” 问题，非常适合使用 二分答案：

• 我们猜测一个最短跳跃距离 mid。
• 判断是否可以通过移走不超过 M 块岩石，使得任意相邻保留岩石之间的距离都不小于 mid。
• 如果可以，则说明答案至少为 mid，尝试更大的值；
• 否则，说明 mid 太大，需要减小。

2. 如何判断一个 mid 是否可行？——贪心模拟

我们从起点开始，贪心地保留岩石，只在必要时移走岩石：

• 维护上一个保留的岩石位置 i（初始为起点 0）。
• 遍历后续岩石（包括终点）：如果当前岩石与 i 的距离 >= mid，就保留它（更新 i）。否则，必须移走这块岩石（计数器 count++）。
• 如果移走的岩石数 <= M，则 mid 可行。

为什么贪心是对的？

因为我们希望尽可能早地保留一块岩石（只要满足距离 ≥ mid），这样留给后面的跳跃空间更大，移走的岩石更少。这是典型的“能留就留”的贪心策略。

3. 二分范围

• 最小可能答案：1（至少跳 1 单位）
• 最大可能答案：L（直接从起点跳到终点）
• 所以二分区间为 [1, L] 或 [0, L]

由于答案是整数，使用整数二分即可，无需浮点。

算法步骤

1. 读入 L, N, M 和岩石位置。
2. 将起点 0 和终点 L 加入数组，并排序（虽然输入已有序，但加了端点后仍需确保顺序）。
3. 二分答案：left = 0, right = Lmid = (left + right + 1) / 2
4. check(mid) 函数模拟跳跃过程，统计需移除岩石数。
5. 输出最终答案。

代码关键

bool check(int mid)
{
    int count = 0;
    int i = 0, j = 1; // i: 上一个保留的位置下标，j: 当前检查的岩石下标
    while (j <= n+1)  // nums[0]=0（起点），nums[n+1]=L（终点）
    {
        if (nums[j] - nums[i] >= mid)
        {
            i = j++;  // 保留 j，更新 i
        }
        else
        {
            count++;  // 移走 j
            j++;
        }
        if (count > m) return false;
    }
    return true;
}

• nums 数组包含：[0, D1, D2, ..., DN, L]，共 N+2 个元素。
• 模拟过程确保起点和终点始终保留。
• 一旦移走数量超过 M，立即返回 false。

主函数中使用标准整数二分模板，寻找满足 check(mid) 的最大 mid。

示例验证

输入：

25 5 2
2
11
14
17
21

岩石位置（含端点）：[0, 2, 11, 14, 17, 21, 25]

若 mid = 4：

• 0 → 11（跳过 2，移走1块）
• 11 → 17（跳过14，移走第2块）
• 17 → 21（距离=4 ≥4，保留）
• 21 → 25（距离=4 ≥4）

共移走 2 块 ≤ M=2，可行。

若 mid = 5：

• 0→11（ok）
• 11→17（6≥5，ok）
• 17→21（4<5，需移走21）
• 17→25（8≥5，ok） 但还需检查中间是否超限……实际上会发现需要移走 >2 块，不可行。

因此最大可行 mid = 4，输出 4。

复杂度分析

• 二分次数：O(log L)，L <= 10^9 → 约 30 次
• 每次 check：O(N)
• 总复杂度：O(N log L)，对 N = 50000 完全可行。

总结

本题是二分答案 + 贪心验证的经典应用。核心在于：

• 将“最大化最短跳跃距离”转化为判定性问题；
• 用贪心策略高效验证某个距离是否可达；
• 利用整数二分快速逼近最优解。