跳房子

GitHub跳转原题关系图 Canvas 关系图返回列表

把每个可选落点产生的后退位置视为 BFS 转移，并用并查集删除已扫描落点，使所有区间转移近线性完成。

OJ: shumeng

题目 ID: CSP202412D

难度:普及+/提高-

标签:BFS并查集区间遍历最短路

日期: 2026-07-31 16:21

形式化题目

站在格子 $i$ 时，可以跳到区间 $[i+1, \min(n, i+k_i)]$ 中的任意落点 $j$ ；落到 $j$ 后立即后退 $a_j$ 格，下一次实际站在 $j - a_j$ 。

求从格子 $1$ 跳到格子 $n$ 的最少跳跃次数，不可达输出 $-1$ 。

思路

把每个状态 $i$ 到落点 $j$ 的跳跃看成转移 $i \to j - a_j$ ，问题就是一个 BFS 最短路。难点在于避免重复扫描同一段区间内的落点。

朴素做法：直接枚举落点

先看直接 BFS：对每个出队状态枚举区间内所有落点，做转移。

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/**
 * 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-07-31 16:21
 * update_at: 2026-08-17 22:39
 */
// brute.cpp：小数据暴力解，BFS 中直接枚举当前状态能跳到的所有落点，最坏 O(n^2)。
#include <bits/stdc++.h>
using namespace std;

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

    int n;
    cin >> n;
    vector<int> a(n + 1);
    vector<long long> k(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> k[i];

    vector<int> distance_to(n + 1, -1);
    queue<int> states;
    distance_to[1] = 0;
    states.push(1);

    while (!states.empty()) {
        int current = states.front();
        states.pop();
        // 枚举区间内每个落点 j，落到 j 后退回 j-a[j]
        long long right = min((long long)n, current + k[current]);
        for (int landing = current + 1; landing <= right; landing++) {
            int next_state = landing - a[landing];
            if (distance_to[next_state] == -1) {
                distance_to[next_state] = distance_to[current] + 1;
                states.push(next_state);
            }
        }
    }

    cout << distance_to[n] << '\n';
    return 0;
}

同一落点 $j$ 可能被许多状态的跳跃区间重复覆盖，最坏 $O(n^2)$ 。

关键观察：落点只需处理一次

BFS 按距离从小到大出队。对于某个落点 $j$ ，第一次有状态的跳跃区间覆盖它时，已经用到了能到达该状态的最小跳数；之后从更晚出队的状态使用同一个 $j$ 不可能得到更短路径。因此每个落点只处理一次即可。

用并查集跳过已处理的落点

维护一个并查集表示“下一个还未处理的落点”：

find(x) 返回不小于 $x$ 的最小未删除下标；
处理完落点 $j$ 后删除它，令它指向 find(j+1)；
处理状态 $i$ 时，从 find(i+1) 开始逐个处理，直到超过 $\min(n, i + k_i)$ 。

处理落点 $j$ 时令 $v = j - a_j$ ；若 $v$ 未访问则入队并记录距离。注意删除的是落点下标而不是状态下标，所以多个落点后退到同一个状态也不会出错。

样例推演

下表记录样例一的 BFS 过程，落点只在第一次被扫描时出现：

出队状态	跳数	本次处理的落点及转移	新入队状态
1	0	`2 -> 1`，`3 -> 2`	`2`
2	1	`4 -> 3`，`5 -> 4`，`6 -> 3`	`3, 4`
3	2	`7 -> 6`，`8 -> 8`	`6, 8`
4	2	无（落点已删除）	无
6	3	`9 -> 6`，`10 -> 10`	`10`

状态 10 首次以距离 $4$ 入队，答案为 $4$ 。状态 8 后续即使再覆盖部分落点，也不会改变已经得到的答案。

代码

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
65/**
 * 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-07-31 16:21
 * update_at: 2026-08-17 22:39
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

int n;
int a[MAXN];
long long k[MAXN];
int distance_to[MAXN];
int next_unused[MAXN];

int find_next(int x) {
    int root = x;
    while (next_unused[root] != root) root = next_unused[root];
    while (next_unused[x] != x) {
        int next = next_unused[x];
        next_unused[x] = root;
        x = next;
    }
    return root;
}

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

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> k[i];

    for (int i = 1; i <= n; i++) distance_to[i] = -1;
    for (int i = 2; i <= n + 1; i++) next_unused[i] = i;

    queue<int> states;
    distance_to[1] = 0;
    states.push(1);

    while (!states.empty()) {
        int current = states.front();
        states.pop();

        long long right = min((long long)n, current + k[current]);
        int landing = find_next(current + 1);
        while (landing <= right) {
            // 落点 landing 只保留第一次被某个最短路状态扫描的机会。
            next_unused[landing] = find_next(landing + 1);
            int next_state = landing - a[landing];
            if (distance_to[next_state] == -1) {
                distance_to[next_state] = distance_to[current] + 1;
                states.push(next_state);
            }
            landing = find_next(landing);
        }
    }

    cout << distance_to[n] << '\n';
    return 0;
}

复杂度

时间：每个落点只被删除一次，并查集 find 均摊近常数，总复杂度 $O(n \alpha(n))$ 。
空间： $O(n)$ 。

总结

区间转移题的难点不是 BFS 本身，而是避免重复扫描区间内的落点。BFS 提供“第一次覆盖落点时距离最优”的顺序保证，并查集把所有已处理落点跳过，从而把大量区间枚举压缩成一次近线性的删除过程。

图示解析

这张流程图概括每个 BFS 状态的处理方式：

text

1
2
3
4
5出队状态 i
|- 确定落点区间 [i+1, min(n, i+k_i)]
   `- 并查集找到区间内尚未处理的 j
      |- 删除 j，转移到 j-a[j]
      `- 未访问状态入队

落点 $j$ 被处理后不会再次参与后续区间扫描。因为 BFS 出队距离单调不减，后面状态通过同一落点得到的路径不可能更短。

题目来自第 36 次 CSP 认证 T4，评测使用自造高质量复刻数据。我们承认原始题面与大样例版权均归中国计算机学会（CCF）所有，因此题面与评测服务均免费对外开放。如果您认为我们侵犯了您的权益，可联系我们。

时间限制： 0.5 秒

空间限制： 512 MB

题目描述

跳房子游戏是西西艾弗岛上孩子们的传统娱乐方式。今天小 P 造访了西西艾弗岛，小 C 向他示范了跳房子游戏该怎么玩。

在地面上有一字排开的 $n$ 个格子，每个格子上都写着一个数字，第 $i$ 个格子上写着的数字是 $a_i$ 。这些数字满足 $a_i<i$ 且 $a_n=0$ 。

一开始，小 C 站在第一个格子上。小 C 是一个擅长跳跃的人，他可以往前跳很远，但为了游戏的趣味性，小 C 规定在第 $i$ 个格子上最多能往前跳 $k_i$ 格，而且不能跳到第 $n$ 个格子后面。也就是说，如果小 C 现在站在第 $i$ 个格子上，那么他可以跳到第 $i+1$ 个格子和第 $\min(n,i+k_i)$ 个格子之间的任意格子上。

根据跳房子游戏的规则，如果小 C 在一次跳跃之后落到了第 $i$ 个格子上，那么他需要后退 $a_i$ 格，也就是说小 C 在跳跃后会站在第 $i-a_i$ 个格子上。

玩了一会之后，小 P 突然好奇，小 C 最少需要跳多少次才能到达第 $n$ 个格子呢？小 C 也不知道这个答案，于是他只能来请教你。

输入格式

从标准输入读入数据。

第一行一个正整数 $n$ ，代表格子的数量。

第二行 $n$ 个非负整数 $a_1, a_2, \dots, a_n$ ，其中 $a_i$ 表示第 $i$ 个格子上的数字。

第三行 $n$ 个非负整数 $k_1, k_2, \dots, k_n$ ，其中 $k_i$ 表示小 C 在第 $i$ 个格子时能往前跳的最大格数。

输出格式

输出到标准输出。

输出一行一个整数表示小 C 到达第 $n$ 个格子需要的最少跳跃次数，如果小 C 不能到达第 $n$ 个格子输出 $-1$ 。

input1

1
2
310
0 1 1 1 1 3 1 0 3 0
2 4 5 4 1 4 1 3 5 3

output1

样例 1 解释

从第 $1$ 个格子出发，首先往前跳 $2$ 格到第 $3$ 个格子，然后后退一格，停在第 $2$ 个格子。

从第 $2$ 个格子往前跳 $3$ 个格子到第 $5$ 个格子，后退一格，停在第 $4$ 个格子。

从第 $4$ 个格子往前跳 $4$ 个格子到第 $8$ 个格子，不需要后退，停在第 $8$ 个格子。

从第 $8$ 个格子往前跳两格即到达第 $10$ 个格子。总共跳跃 $4$ 次。

input2

1
2
35
0 1 2 3 0
3 4 4 10 15

output2

1-1

子任务

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。

子任务 1（30 分）：保证 $n \le 1000$ ；
子任务 2（30 分）：保证 $\forall 1 \le i < j \le n$ 都有 $k_i \le k_j$ ；
子任务 3（40 分）：无特殊限制。

对于所有数据，保证 $1 \le n \le 10^5,~ 0 \le a_i < i,~ 1 \le k_i \le 10^9$ 。

提示

本题输入量较大，请采用效率较高的读入方式。

跳房子

目录