B4246 [语言月赛 202503] 环形游走 题解

Maxmilite · 2025-03-19 17:00:44 · 题解

[语言月赛 202503] 环形游走 题解

Source & Knowledge

本题来源于 2025 年 3 月的语言月赛，主要考察简单一维数组的运用。

文字题解

题目描述了一种环形游走的方式，老师从第 1 号小朋友开始，按照逆时针方向，移动 m 次，每次的步数由当前位置小朋友衣服上的数字决定。由于小朋友是围成一圈的，因此当位置小于 1 时，需要回到最后一个小朋友。

首先按照题目要求读入 n, m 和 a 数组：

int a[5005]; // n 最大是 5000，因此这里开的比 5000 略大一些。
// 一般建议定义全局数组，即，上述语句建议写在 main 函数外
int n, m;

// main 函数内
cin >> n >> m;
for (int i = 1; i <= n; i++) {
    cin >> a[i];
}

之后，我们可以使用一个 \text{pos} 变量，记录老师的位置。老师的起始位置是 1 号小朋友，因此 \text{pos} 初始值为 1。

接下来模拟移动过程。我们循环做 m 次如下操作：

• 读取当前位置小朋友衣服上的数字 a_{\text{pos}}，计算新的位置。

• 由于是逆时针移动，每次移动 a_{\text{pos}} 步，新的位置计算方式如下：

  \text{pos} = \text{pos} - a_{\text{pos}}

• 如果 \text{pos} \leq 0，表示已经超出了第 1 号小朋友，需要重新回到小朋友处。方法是，将 \text{pos} 加上若干个 n，直到 \text{pos} 重新回到 1 \sim n 的范围内。

  【坑点】此处的一个坑点是，因为 a_{\text{pos}} 很有可能远大于 n，所以只在 \text{pos} 上加一个 n 是不够的。我们需要不断在 \text{pos} 上 + n，直到 \text{pos} 不再 \leq 0 为止。

   while (pos <= 0) {
      pos += n;
   }

• 进行 m 次移动后，最终位置即为答案。

int pos = 1;
for (int j = 1; j <= m; j++) {
    pos -= a[pos];
    while (pos <= 0) pos += n;
}
cout << pos << endl;