[语言月赛 202401] 跳房子 题解

· · 题解

Source & Knowledge

2024 年 1 月语言月赛，由洛谷网校入门计划/基础计划提供。

题目大意

一行 n 个格子，每个格子上有一个整数 a _ i。从 1 号点起跳，每次从 i 号点跳到 a _ i + i 的位置。当跳跃到 \geq n 号位后停止跳跃。求问能否恰好跳到 n 号位，一共条约多少次。

题目分析

本题考察对循环结构的运用。

由于 a _ i \geq 1，因此每一次一定有 i + a _ i > i，因此玩家一定会不断向右跳跃。

不使用数组的做法是，使用一个变量 c（初始值为 1）记录当前所在的位置。在循环读入 for (int i = 1; i <= n; ++i) { cin... } 的过程中，如果 i = c，则让 c 变为 c + x（x 是当前循环读入的变量）即可。

在过程中同时使用一个变量记录跳跃次数。当 c 有变化时使变量自增 1 即可。最终输出 c 是否等于 n 以及记录跳跃次数的变量即可。

核心代码如下：

int c = 1, cnt = 0;
for (int i = 1; i <+ n; ++i) {
    cin >> x;
    if (c == i) {
        c = c + x;
        ++cnt;
    }
}
if (c == n) {
    cout << "Yes" << endl;
} else {
    cout << "No" << endl;
}
cout << cnt << endl;

视频讲解