luogu-P2678 跳石头

NOIP 2015 提高组 Day2 真题，二分答案的经典入门题。通过二分搜索"最短跳跃距离的最大值"，再用贪心策略验证可行性。适合GESP六级以上考生练习。题目难度⭐⭐⭐，洛谷难度等级普及。

luogu-P2678 [NOIP 2015 提高组] 跳石头

题目要求

题目描述

一年一度的"跳石头"比赛又要开始了！
这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有 $N$ 块岩石（不含起点和终点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。
为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走 $M$ 块岩石（不能移走起点和终点的岩石）。

输入格式

第一行包含三个整数 $L,N,M$ ，分别表示起点到终点的距离，起点和终点之间的岩石数，以及组委会至多移走的岩石数。保证 $L \geq 1$ 且 $N \geq M \geq 0$ 。
接下来 $N$ 行，每行一个整数，第 $i$ 行的整数 $D_i\,( 0 < D_i < L)$ ，表示第 $i$ 块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出，且不会有两个岩石出现在同一个位置。

输出格式

一个整数，即最短跳跃距离的最大值。

输入输出样例 #1

输入 #1

输出 #1

说明/提示

输入输出样例 1 说明

将与起点距离为 $2$ 和 $14$ 的两个岩石移走后，最短的跳跃距离为 $4$ （从与起点距离 $17$ 的岩石跳到距离 $21$ 的岩石，或者从距离 $21$ 的岩石跳到终点）。

数据规模与约定

对于 $20\%$ 的数据， $0 \le M \le N \le 10$
对于 $50\%$ 的数据， $0 \le M \le N \le 100$
对于 $100\%$ 的数据， $0 \le M \le N \le 50000$ ， $1 \le L \le 10^9$

题目分析

本题是二分答案的经典入门题。题目要求"最短跳跃距离的最大值"——这种"最小值最大化"或"最大值最小化"的问法，几乎就是在告诉我们：用二分答案来做。

1. 为什么想到二分答案？

我们先分析问题的结构：

如果我们规定"最短跳跃距离至少为 $d$ "，那么所有距离小于 $d$ 的相邻岩石之间的间隔都不合格，需要通过移走某些岩石来消除这些"过短的间隔"。
当 $d$ 越大，需要移走的岩石就越多； $d$ 越小，需要移走的岩石就越少。

这说明" $d$ 是否可行"具有单调性：存在一个临界值，小于等于它的 $d$ 都可行（移走的岩石不超过 $M$ 块），大于它的 $d$ 都不可行。这个临界值就是我们要求的答案。

有了单调性，就可以用二分查找高效定位这个临界值。

2. 二分答案的框架

二分的对象是最短跳跃距离 $d$ ，搜索范围为 $[1, L]$ ：

下界 $1$ ：最短跳跃距离至少为 $1$ （岩石坐标各不相同且为正整数）
上界 $L$ ：最短跳跃距离最多为 $L$ （把所有中间岩石都移走，直接从起点跳到终点）

对于每个候选值 $mid$ ，我们需要一个验证函数 check(mid)：判断"能否在最多移走 $M$ 块岩石的前提下，使得所有相邻跳跃距离都 $\ge mid$ "。

如果 check(mid) 返回 true（可行），说明答案 $\ge mid$ ，继续尝试更大的值
如果 check(mid) 返回 false（不可行），说明答案 $< mid$ ，缩小搜索范围

3. 验证函数 check(mid)——贪心模拟

验证函数的核心思路是贪心：从起点出发，按顺序扫描每块岩石，决定是保留还是移走。

贪心策略如下：

维护一个变量 last 表示上一块保留的岩石的位置（初始为起点 $0$ ）
依次考察每块岩石 $D_i$ $D_{i}$ ：
- 如果 $D_i - last < mid$ （当前岩石与上一块保留的岩石距离不够），则移走当前岩石，移走计数 +1
- 否则（距离足够），保留当前岩石，更新 $last = D_i$
最终判断：移走的总数是否 $\le M$

为什么贪心是正确的？ 当我们遇到一个"距离太近"的岩石时，移走它一定不会比保留它更差。因为保留它会使后续岩石与它的距离更近（更容易造成"距离不足"），而移走它则相当于把间隔"合并"给后续岩石，留下更大的余量。

4. 样例验证

样例： $L = 25, N = 5, M = 2$ ，岩石位置： $2, 11, 14, 17, 21$

加上起点 $0$ 和终点 $25$ ，完整序列为： $0, 2, 11, 14, 17, 21, 25$

相邻间距为： $2, 9, 3, 3, 4, 4$

二分过程（关键步骤）：

当 $mid = 4$ 时，执行贪心验证：

步骤	考察岩石	与 `last` 的距离	$\ge 4$ ?	操作	`last`	移走计数
1	$D_1 = 2$	$2 - 0 = 2$	否	移走	$0$	$1$
2	$D_2 = 11$	$11 - 0 = 11$	是	保留	$11$	$1$
3	$D_3 = 14$	$14 - 11 = 3$	否	移走	$11$	$2$
4	$D_4 = 17$	$17 - 11 = 6$	是	保留	$17$	$2$
5	$D_5 = 21$	$21 - 17 = 4$	是	保留	$21$	$2$

最后检查终点： $25 - 21 = 4 \ge 4$ ，合格。移走 $2$ 块 $\le M = 2$ ，可行。

保留的岩石为 $0, 11, 17, 21, 25$ ，相邻跳跃距离为 $11, 6, 4, 4$ ，最短距离为 $4$ 。

当 $mid = 5$ 时，贪心验证会需要移走超过 $2$ 块岩石，不可行。

因此答案为 $4$ ，与样例输出一致。

5. 复杂度分析

二分查找： $O(\log L)$ 轮
每轮验证： $O(N)$ ，线性扫描所有岩石
总时间复杂度： $O(N \log L)$

在本题数据范围下（ $N \le 50000, L \le 10^9$ ）， $\log_2(10^9) \approx 30$ ，总运算量约为 $50000 \times 30 = 1.5 \times 10^6$ ，远在时限内。

空间复杂度： $O(N)$ ，存储岩石坐标

示例代码

#include <iostream>

// 岩石位置数组（下标 0 存起点，1~N 存中间岩石，N+1 存终点）
int d[50005];

int main() {
    int L, N, M;
    std::cin >> L >> N >> M;

    // 读入 N 块岩石的位置
    for (int i = 1; i <= N; i++) {
        std::cin >> d[i];
    }

    // 起点和终点
    d[0] = 0;
    d[N + 1] = L;

    // 二分答案：搜索"最短跳跃距离"的最大值
    int lo = 1, hi = L, ans = 0;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;

        // 贪心验证：最短跳跃距离至少为 mid 时，需要移走多少块岩石
        int removed = 0; // 移走的岩石计数
        int last = 0;    // 上一块保留的岩石的位置（从起点开始）
        for (int i = 1; i <= N; i++) {
            if (d[i] - last < mid) {
                // 当前岩石与上一块保留的岩石距离不够，移走
                removed++;
            } else {
                // 距离足够，保留当前岩石
                last = d[i];
            }
        }
        // 检查最后保留的岩石到终点的距离
        if (L - last < mid) {
            removed++;
        }

        // 判断可行性
        if (removed <= M) {
            // 移走的岩石数不超过 M，mid 可行，尝试更大的值
            ans = mid;
            lo = mid + 1;
        } else {
            // 需要移走的岩石太多，mid 不可行，缩小搜索范围
            hi = mid - 1;
        }
    }

    std::cout << ans << std::endl;
    return 0;
}

拓展思考

二分答案的适用场景

本题是"最小值最大化“问题的典型代表。以下特征出现时，应该首先考虑二分答案：

求最优值（最大化/最小化某个量）
判定问题比优化问题简单：直接求最优解很难，但给定一个候选答案后，验证其可行性却很容易（通常用贪心或简单模拟）
单调性：候选答案和可行性之间存在单调关系

题目	类型	要点
P2678 跳石头（本题）	二分答案	最小值最大化，贪心验证移走岩石数
P1182 数列分段	二分答案 + 贪心	最大值最小化，贪心分段验证
P1824 进击的奶牛	二分答案 + 贪心	最小距离最大化，与跳石头非常相似
P3853 路标设置	二分答案 + 贪心	最大间距最小化，添加路标的逆向思维