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
2
3
4
5
6

25 5 2
2
11
14
17
21

输出 #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 - 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$ 时，执行贪心验证：

最后检查终点：$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)$，存储岩石坐标

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

#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;
}

拓展思考

二分答案的适用场景

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

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

推荐练习

掌握”二分答案 + 贪心验证”这一组合技后，能解决大量看似复杂的优化问题，这是竞赛和考试中的高频考点。

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

GESP 学习专题站：GESP WIKI

"luogu-"系列题目可在洛谷题库进行在线评测。

"bcqm-"系列题目可在编程启蒙题库进行在线评测。

欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答

欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总

欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助