形式化题目

数轴上起点 $0$ 与终点 $L$ 固定且不可移走，中间有 $N$ 个互异的可移除岩石 $D_1 < D_2 < \cdots < D_N$（$0 < D_i < L$）。移除至多 $M$ 个岩石后，从 $0$ 依次跳到保留岩石再到 $L$；每一步的距离是相邻保留点（含端点）之差。 求移除后路径中最小步距的最大值。

等价地：求最大的 $x$，使存在一个保留集合，让所有相邻间隔（含 $0$ 到首保留点、 末保留点到 $L$）都 $\geqslant x$，且移除数 $\leqslant M$。

样例 $L=25,\ N=5,\ M=2$，岩石 $2, 11, 14, 17, 21$。对候选答案 $x$ 做贪心判定 （last 为上一个保留点，limit = L - x 是保留点最右允许位置）：

$x=4$ 删 $2$ 个 $\leqslant M=2$，可行（末跳 $25-21=4$）；$x=5$ 要删 $3$ 个 $> M$，不可行。所以答案是 $4$。

正解

思路

朴素做法与瓶颈。 最直接的两个朴素路线都走不通：枚举移除方案要 $\binom{N}{M}$ 种，$N = 5\times10^4$ 完全爆炸；把"对答案逐点枚举 + 贪心判定" 拼起来，判定虽然只要 $O(N)$，但答案域是 $10^9$，要试 $10^9$ 次。两者共享同一个 可利用的结构——可行性关于 $x$ 单调：若某套保留点让所有间隔 $\geqslant x$， 它对任何 $x' \leqslant x$ 同样合法。于是可行域是前缀 $[1, x^*]$，"求最大可行 $x$"就是找可行与不可行的分界点，对半排除即可，瓶颈从"答案域 $10^9$"降到 “$\log_2 10^9 \approx 30$ 次判定”。

第一步：$O(N)$ 的贪心判定。 给定 $x$，令 limit = L - x，从 last = 0 从左往右扫：

• d > $ `limit`：删。终点不可移走，保留它则末跳 $1lt; x；删掉它只会让保留点 更靠左，对后面更有利。这是本题最容易漏的端点条件——只判相邻间距会漏检 最后一跳（如 $L=10$、岩石 $[9]$、$M=0$ 判 $x=5$：间距都够，但 $0 \to 9 \to 10$ 的末跳只有 $1$）。
• $d - \text{last} < x$：删。
• 否则保留，last = d。

贪心保留"最早可行"的点是最优的：设贪心第 $i$ 个保留点 $g_i$、任意可行方案第 $i$ 个保留点 $s_i$，归纳可证 $g_i \leqslant s_i$（$g_1$ 是首个 $\geqslant x$ 的岩石， 显然更靠左；$g_i \leqslant s_i \Rightarrow g_{i+1} \leqslant s_i + x \leqslant s_{i+1}$）。 保留点越靠左，后面的约束越松，所以任何可行方案保留的岩石数都不超过贪心—— 贪心计数正是最少移除数，且所有保留点 $\leqslant$ limit 保证末跳自动 $\geqslant x$。need_remove(x) <= M 与"存在合法方案"完全等价。

第二步：对答案二分。 need_remove(x) 关于 $x$ 单调不减（$x$ 变大， limit 变小、间距条件更严），在 $[1, L]$ 上闭区间二分：mid 可行抬 lo， 不可行压 hi，lo == hi 即最大可行值。样例收敛过程（$4$ 轮）：

lo == hi == 4，输出 $4$。初始化 lo = 1 安全（岩石位置互异整数，全部保留 时最小间隔 $\geqslant 1$，$x=1$ 恒可行）；hi = L 可达（$x=L$ 时 limit = 0， 全部岩石必删，$M=N$ 时恰好可行），$N=0$ 与 $M=N$ 都无需特判。

代码

Python 版：

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#!/usr/bin/env python3
# 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-09-30 01:32
# update_at: 2026-09-30 01:32

import sys


def need_remove(stones: list[int], mid: int, length: int) -> int:
    """贪心：保证每一段跳跃距离 >= mid 时，最少需要移走的岩石数。

    两处都要删：与上一个保留点距离不足 mid 的岩石；以及越过 limit 的岩石
    （终点跳不了「倒数保留点 -> 终点」这段，必删——终点不可移走）。
    从左往右保留最早可行的岩石，上一个保留点最靠左，后面可选空间最大，故最优。
    """
    limit = length - mid  # 保留点最远只能到 L - mid，否则最后一跳不足 mid
    removed = 0
    last = 0  # 上一个保留点（起点）
    for d in stones:
        if d > limit or d - last < mid:
            removed += 1
        else:
            last = d
    return removed


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    length = next(data)  # 起点到终点的距离 L
    n = next(data)       # 岩石数 N
    m = next(data)       # 最多移走 M 个
    stones = [next(data) for _ in range(n)]  # 输入已按距离升序

    # 答案越大越难满足，对答案二分；need_remove 随 mid 单调不减
    lo, hi = 1, length
    while lo < hi:
        mid = (lo + hi + 1) // 2
        if need_remove(stones, mid, length) <= m:
            lo = mid  # mid 可行，抬高下界
        else:
            hi = mid - 1

    print(lo)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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/**
 * 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-04 23:29
 * update_at: 2026-10-04 23:29
 */
#include <cstdio>

typedef long long ll;

const ll MAXN = 50005;

ll L, n, m;              // 河道长 L，中间岩石数 n，最多移走 m 个
ll d[MAXN];              // d[i] = 第 i 个岩石到起点的距离（输入已升序）

// 判定：要求最短跳跃距离 >= x 时，最少需要移走几个岩石
// 从左往右贪心保留"最早可行"的岩石，保留点越靠左后面越宽松，所以是最优的
ll need_remove(ll x) {
    ll limit = L - x;    // 保留点最远只能到 L-x，否则最后一跳不足 x
    ll removed = 0;
    ll last = 0;         // 上一个保留点，起点从 0 开始
    for (ll i = 1; i <= n; ++i) {
        // 越过 limit 的岩石必删：终点不可移走，末跳必须 >= x
        // 与上一个保留点距离不足 x 的也要删
        if (d[i] > limit || d[i] - last < x)
            ++removed;
        else
            last = d[i];
    }
    return removed;
}

int main() {
    scanf("%lld %lld %lld", &L, &n, &m);
    for (ll i = 1; i <= n; ++i)
        scanf("%lld", &d[i]);

    // 对答案二分：need_remove(x) 随 x 单调不减，可行域是前缀 [1, x*]
    // 岩石位置互异整数，x=1 恒可行；x=L 时全删，M=N 时可达
    ll lo = 1, hi = L;
    while (lo < hi) {
        ll mid = (lo + hi + 1) / 2;   // 上取整，lo 只被可行解抬高，不会死循环
        if (need_remove(mid) <= m)
            lo = mid;                 // mid 可行，抬高下界
        else
            hi = mid - 1;
    }

    printf("%lld\n", lo);
    return 0;
}

复杂度

• 时间复杂度：$O(N \log L)$：二分至多 $\lceil\log_2 10^9\rceil = 30$ 轮，每轮 扫一遍 $N \leqslant 5\times10^4$ 的岩石，合计约 $1.5\times10^6$ 次比较， 与 C++ 正解（同为二分答案 + 贪心判定）同阶。
• 空间复杂度：$O(N)$：一次读入存全部岩石，判定只用常数个变量。

总结

• "最大化最小步距 / 最大化可行距离"是二分答案的信号：先写出 $O(N)$ 的单调 判定（所需最少移除数 $\leqslant M$），再对答案域对半排除；判定便宜、答案域 $10^9$ 大，二分收益最大。
• 链上删点的贪心判定要两端都收口：左端从 last = 0 起扫，右端必须先删 越过 L - mid 的岩石——终点不可移走，最后一跳没人替你检查。
• 闭区间二分用 mid = (lo + hi + 1) // 2 上取整，lo 只被可行解抬高，不会 在 lo == hi - 1 时死循环。
• 真实数据 10 个测点全部一致：单点 0.015–0.047 s、峰值内存约 14–20 MB， 对 1000 ms / 128 MB 的限制十分宽裕（本地验证放宽 10 倍限时，不声称官方 AC）。