[NOIP 2015 提高组] 跳石头

题意

有一条长为 L 的河道，起点和终点固定，中间有 N 块岩石。你最多可以移走 M 块中间岩石，要求剩余相邻点之间的最短跳跃距离尽可能大。

思路

先看一个可以直接验证想法的朴素解：

在小数据上，我们可以把答案 d 从小到大往上试，只要它还可行就继续增大，直到第一次不可行。前一个可行值就是答案。

cpp

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#include <bits/stdc++.h>
using namespace std;

const int MAXN = 50000 + 5;

long long L;
int N, M;
long long stone[MAXN];

bool check(long long d) {
    long long removed = 0;
    long long last = 0;

    for (int i = 1; i <= N + 1; i++) {
        if (stone[i] - last < d) {
            removed++;
        } else {
            last = stone[i];
        }
        if (removed > M) return false;
    }

    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> L >> N >> M;
    for (int i = 1; i <= N; i++) cin >> stone[i];
    sort(stone + 1, stone + N + 1);
    stone[N + 1] = L;

    long long ans = 0;
    while (ans + 1 <= L && check(ans + 1)) {
        ans++;
    }

    cout << ans << '\n';
    return 0;
}

下面是另一种「01 序列」风格的暴力写法。它按石头编号依次决定移走或保留，递归生成完整选择后，叶子节点统一检查移走数量是否不超过 M，并统计当前最短跳跃距离：

另一种暴力写法：01 序列

cpp

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
55
56
57
58
59
60
61
62
63
64// brute_01_style.cpp：01 序列风格暴力，按石头编号依次决定移走或保留。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 25;

long long L;
int N, M;
long long stone[MAXN];
int keep_stone[MAXN]; // keep_stone[i] 表示第 i 块中间石头是否保留。
long long answer;

bool check() {
    int removed = 0;
    for (int i = 1; i <= N; i++) {
        if (keep_stone[i] == 0) removed++;
    }
    return removed <= M;
}

long long calc_min_jump() {
    long long last = 0;
    long long best = L;
    for (int i = 1; i <= N; i++) {
        if (keep_stone[i]) {
            best = min(best, stone[i] - last);
            last = stone[i];
        }
    }
    best = min(best, L - last);
    return best;
}

void dfs_choose(int dep) {
    if (dep == N + 1) {
        if (check()) {
            answer = max(answer, calc_min_jump());
        }
        return;
    }

    // 第 dep 块石头的 01 选择：0 移走，1 保留。
    for (int i = 0; i <= 1; i++) {
        keep_stone[dep] = i;
        dfs_choose(dep + 1);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> L >> N >> M;
    for (int i = 1; i <= N; i++) {
        cin >> stone[i];
    }
    sort(stone + 1, stone + N + 1);

    answer = 0;
    dfs_choose(1);

    cout << answer << '\n';
    return 0;
}

这个朴素解的问题在于，d 的范围最大可以到 L，直接枚举会太慢。但它已经把题目拆成了两个部分：

固定一个距离 d，怎么判断它能不能做到；
如何更快地找到最大的可行 d。

对于第一个问题，排序后从左到右贪心扫描即可。如果当前石头和上一个保留点的距离已经小于 d，那这块石头只能删除。这样一来，固定 d 时需要删除的最少石头数就能被算出来。

有了这个可行性判断以后，就可以对答案二分。因为 d 越大越难满足，所以“是否可行”具有单调性：可行的 d 之前都可行，不可行的 d 之后都不可行。

Python 知识

stones = positions + [length] 把终点并入同一次扫描，避免循环结束后再写一段特殊判断。
Python 的 for position in stones 直接遍历位置值，不需要维护 C++ 数组下标。
previous 保存上一个保留点；距离不足时只增加删除数，否则更新保留点。
/home/rainboy/mycode/hugo-blog/content/program_language/python/oj_input_output_cheatsheet.md：按 token 读取整数并用切片取得石头位置。

代码

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
28import sys


data = list(map(int, sys.stdin.buffer.read().split()))
length, n, limit = data[:3]
stones = data[3:3 + n] + [length]


def possible(distance):
    removed = 0
    previous = 0
    for position in stones:
        if position - previous < distance:
            removed += 1
        else:
            previous = position
    return removed <= limit


left, right = 0, length
while left < right:
    middle = (left + right + 1) // 2
    if possible(middle):
        left = middle
    else:
        right = middle - 1

print(left)

复杂度

排序复杂度是 $O(N log N)$ 。每次检查是 $O(N)$ ，二分次数是 $O(log L)$ 。

所以总时间复杂度是 $O(N log N + N log L)$ ，空间复杂度是 $O(N)$ 。

总结

这题的关键是把“最短跳跃距离最大化”转成“答案二分”。对于固定距离，用贪心扫描统计最少删除数，就能快速判断这个距离是否可行。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。