形式化题目

在数轴上，起点位于 $0$，终点位于 $L$，两者之间有 $N$ 块岩石，第 $i$ 块与起点的距离为 $D_i$，所有 $D_i$ 互不相同且 $0 < D_i < L$。可以移走其中至多 $M$ 块岩石（起点和终点不能移走）。移走之后，从起点出发沿保留的岩石跳到终点，把每相邻两个保留位置之间的距离的最小值记为「最短跳跃距离」。求移走至多 $M$ 块岩石时，最短跳跃距离的最大值。

样例：$L=25$，岩石 $\{2,11,14,17,21\}$，$M=2$。移走 $2$ 和 $14$ 后，保留序列为 $0,11,17,21,25$，相邻距离为 $11,6,4,4$，最短跳跃距离为 $4$。可以证明这是最优答案。

正解

思路

朴素做法：枚举移走哪些岩石（组合数 $\binom{N}{M}$，指数级），对每种方案算最小间隔取最大。$N \leqslant 5 \times 10^4$ 时完全不可行，必须换角度。

第一步：把「最大化最小值」转化为判定问题。 直接求「最短跳跃距离的最大值」很难，但它具有单调性——如果我们问「最短跳跃距离能否达到 $x$」，那么：

• $x$ 越大，要求越苛刻，可行方案越少；
• 定义 $f(x)$ = 使所有相邻距离 $\geqslant x$ 时至少要移走的岩石数，则 $x$ 越大 $f(x)$ 越大。

所以存在一个临界值 $x^\ast$：$f(x) \leqslant M$ 当且仅当 $x \leqslant x^\ast$，而 $x^\ast$ 就是答案。于是二分答案 $x \in [1, L]$，剩下的关键就是快速计算 $f(x)$。

第二步：贪心判定。 从左到右扫描（起点、岩石、终点统一看待），维护「上一块保留岩石的位置」$\mathit{prev}$，初始为 $0$：

• 若当前位置 $p$ 与 $\mathit{prev}$ 的距离 $< x$：移走当前岩石（计数 $+1$），$\mathit{prev}$ 不变；
• 否则保留当前岩石，$\mathit{prev} \gets p$。

为什么移走当前岩石而不是更左边的？当 $p - \mathit{prev} < x$ 时，必须在这段间隙里删掉若干岩石。无论删的是 $p$ 还是它左边的某块，间隙都会变宽；但删当前岩石能让后续岩石到上一保留点的距离尽可能大，对后面的判定只赚不亏（交换论证：任何可行方案保留的某块岩石，贪心保留的对应岩石位置不会更靠右，因此贪心用掉的删除次数不会超过任何可行方案）。这样统计出的删除次数就是 $f(x)$ 的最小值。

终点不能移走怎么办？ 把终点 $L$ 也放进扫描序列。$x \leqslant L$ 时若终点与 $\mathit{prev}$ 的距离 $< x$，说明这一段必然不可行——扫描到终点时它也会使计数 $+1$，而判定条件 $\mathit{cnt} \leqslant M$ 会因为这个多出来的 $1$ 而更严格，不会把不可行的 $x$ 误判为可行；而可行的 $x$ 下终点必然被保留，计数恰好等于真实删除数。结论：直接把终点当普通位置扫描、判定 $\mathit{cnt} \leqslant M$ 即可。

用样例验证 $x=4$（可行）与 $x=5$（不可行）：

所以答案就是 $4$。

flowchart LR
    A[二分区间 lo=1, hi=L] --> B{mid = lo+hi+1 除以 2}
    B --> C[贪心扫描: 距上一保留点小于 mid 则移走]
    C --> D{移走块数 cnt 小于等于 M ?}
    D -- 是 --> E[lo = mid]
    D -- 否 --> F[hi = mid - 1]
    E --> G{lo 等于 hi ?}
    F --> G
    G -- 否 --> B
    G -- 是 --> H[输出 lo]

代码

1
2
3
4
5
6
7
8
9
10
11
12/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 11:30
 * update_at: 2026-10-10 11:30
 */

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){ios::sync_with_stdio(false);cin.tie(nullptr); int l,n,m; if(!(cin>>l>>n>>m)) return 0; vector<int> pos(n+1); for(int i=0;i<n;i++) cin>>pos[i]; pos[n]=l; int lo=1,hi=l; while(lo<hi){int mid=(lo+hi+1)/2; int cnt=0,prev=0; for(int i=0;i<=n;i++){ if(pos[i]-prev<mid) cnt++; else prev=pos[i]; } if(cnt<=m) lo=mid; else hi=mid-1;} cout<<lo<<'\n'; return 0;}

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"""跳石头：二分答案 + 贪心判定。O(N log L)"""
import sys

def main():
    data = iter(map(int, sys.stdin.buffer.read().split()))
    l, n, m = next(data), next(data), next(data)   # 终点距离 / 岩石数 / 可移走数
    d = [next(data) for _ in range(n)]             # 岩石到起点距离，已升序
    pos = d + [l]                                 # 把终点也看作一块岩石

    def check(x: int) -> bool:
        cnt, prev = 0, 0                # prev = 上一块保留岩石的位置
        for p in pos:                   # 依次考虑每块岩石（含第一块与终点）
            if p - prev < x:            # 距离不足，移走当前岩石
                cnt += 1
            else:
                prev = p                # 保留它
        return cnt <= m                 # 终点不可移走，cnt 天然不含终点被移

    lo, hi = 1, l                       # 答案在 [1, L]
    while lo < hi:
        mid = (lo + hi + 1) // 2
        if check(mid):
            lo = mid
        else:
            hi = mid - 1
    print(lo)

main()

复杂度

• 时间复杂度：$O(N \log L)$。二分 $O(\log L)$ 轮（约 $30$ 轮），每轮贪心扫描 $O(N)$，总计约 $1.5 \times 10^6$ 次操作。
• 空间复杂度：$O(N)$ 存放岩石位置。

总结

• 「最大化最小值」类问题的标准套路：二分答案 + 贪心/搜索判定。判定函数必须单调（这里 $f(x)$ 随 $x$ 单调不减）。
• 贪心判定口诀：从左往右扫，与上一块保留的岩石距离不足 $x$ 就移走当前岩石——移走靠右的一块永远不会更差。
• 终点不可移走的约束不需要特判：把终点加入扫描序列后，不可行的 $x$ 会天然使计数超标。
• 易错点：扫描必须从第一块岩石开始（包含所有 $N$ 块），漏掉第一块会导致答案偏大。