自动搬运

查看原文

来自洛谷，原作者为

	Maxmilite **

搬运于2025-08-24 21:18:06，当前版本为作者最后更新于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;