[语言月赛 202401] 小跳蛙 题解

· · 题解

Source & Knowledge

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

题目大意

给定池塘中的 n 个位置和 n - 1 只小跳蛙（池塘中的空位用 0 表示）。每一次让相应编号的小跳蛙跳到池塘中的空位置上，一共跳跃 n - 1 次。求最终池塘中每个位置的小跳蛙编号。

题目分析

本题考察对数组结构的运用。

可以注意到，第一次时 1 号小跳蛙跳到池塘中的 0 元素位置上，0 元素变为 1，1 位置变为 0；第二次 2 号跳到当前的 0 元素位置上，即跳到初始时的 1 元素位置上。原来的 1 元素经过 1 \to 0 \to 2 的变化。以此类推，最后一只小跳蛙会跳到初始时 n - 1 元素的位置上，n - 1 \to 0 \to n，最终 n 号元素的位置变为 0。

因此可以发现，对于池塘中除 n 号元素位置以外的位置，其中的元素在整个跳跃流程结束后都变为了自身 + ~ 1。而 n 号位置变为了 0。

因此在读入整个数组 a _ 1, a _ 2, \cdots, a _ n 后，从头开始输出 a _ 1 + 1, a _ 2 + 1, \cdots, a _ n + 1 即可，唯一需要注意的就是当 a _ i = n 时需要输出 0。

for (int i = 1; i <= n; ++i) {
    cin >> a[i];
}
for (int i = 1; i <= n; ++i) {
    if (a[i] != n) {
        cout << a[i] + 1 << " ";
    } else {
        cout << 0 << " ";
    }
}

从另一种角度考虑，对于某个位置 i，其中的元素会在 a _ i 撤走后变为 a _ i + 1（除 a _ i = n 的情况外），因此也可以得到与上文一样的结论。

视频讲解