牛牛的跳跳棋

题目描述

一维棋盘编号 $1 \sim n+1$ ，棋子初始在格子 $1$ ，目标是走到格子 $n+1$ ；格子 $i$ 的弹力系数 $p_i$ 允许从 $i$ 跳到 $[i-p_i,\ i+p_i]$ 内的任意一格。游戏开始前可对若干格子各施一次魔法使其 $p_i+1$ ，求最少施法次数及一个按字典序最小的施法格子编号序列。

第一行一个正整数 $n$ ；第二行 $n$ 个非负整数 $p_i$ 。先输出最少施法次数 ans；若 ans>0 再输出一行 ans 个整数表示每次选中的格子编号。

样例 1： $n=12$ ， $p=[5,4,3,3,2,1,0,0,0,1,0,0]$ → 5 ＋ 4 8 9 10 12。 样例 2： $n=8$ ， $p=[0,1,0,1,0,1,0,1]$ → 4 ＋ 1 2 4 6。 样例 3： $n=5$ ， $p=[0,0,0,0,0]$ → 5 ＋ 1 2 3 4 5。 样例 4： $n=5$ ， $p=[1,1,1,1,1]$ → 0（无第二行）。数据范围： $1\le n\le 10^5,\ 0\le p_i\le 100$ 。

思路

从左到右维护"当前不施法能到达的最右格子" reach 与"撑起它的格子" cast_at；扫描到 $i>reach$ 的断档处时，给 cast_at 恰好 $+1$ 把可达前缀接到 $i$ 上，并令 cast_at=i。每补一次断档就施一次法，次数等于断档数最优；cast_at 总是当前最小的可行编号，逐次产出字典序最小序列。终点 $n+1$ 也参与断档检查；ans=0 时只输出一行。

参考代码

Python 版：

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#!/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-10-02 17:23
# update_at: 2026-10-02 17:23

import sys


def solve() -> None:
    """贪心扫描：reach 是当前弹力下能到达的最右格子，cast_at 是撑起它的施法格。"""
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    p = [next(data) for _ in range(n)]  # 弹力系数，p[i-1] 是格子 i 的值

    reach = 1           # 不再施法能到达的最右格子（初始站在格子 1）
    cast_at = 1         # 把 reach 撑到当前值的格子，即断档时应施法的格子
    casts: list[int] = []

    for i in range(1, n + 2):  # 格子 n+1 是终点，也要参与断档检查
        if i > reach:  # 第一次走出可达范围：给 cast_at 施法恰好补上这一格
            casts.append(cast_at)
            p[cast_at - 1] += 1
            reach = cast_at = i
        if i <= n and i + p[i - 1] > reach:  # 格子 i 能把右边界推得更远
            reach = i + p[i - 1]
            cast_at = i

    print(len(casts))
    if casts:
        print(*casts)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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/**
 * 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 21:36
 * update_at: 2026-10-04 21:36
 */

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 100005;

int n;
int p[MAXN + 2]; // p[i] 表示格子 i 的弹力系数；p[n+1] 占位为 0

vector<int> casts; // 每次施法的格子编号

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

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> p[i];
    }
    p[n + 1] = 0;

    int reach = 1;   // 不施法能到达的最右格子（棋子初始在格子 1）
    int cast_at = 1; // 把 reach 撑到当前值的格子，断档时应施法在它身上

    for (int i = 1; i <= n + 1; i++) {
        if (i > reach) {
            // 第一次走出可达范围：给 cast_at 施法恰好补上这一格
            casts.push_back(cast_at);
            reach = cast_at = i;
        }
        if (i <= n && i + p[i] > reach) {
            // 格子 i 能把右边界推得更远
            reach = i + p[i];
            cast_at = i;
        }
    }

    cout << (int)casts.size() << "\n";
    if (!casts.empty()) {
        for (size_t i = 0; i < casts.size(); i++) {
            if (i) cout << " ";
            cout << casts[i];
        }
        cout << "\n";
    }
    return 0;
}

目录

题目描述

思路

参考代码