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

Source & Knowledge

文字题解

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

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

• 读取当前位置小朋友衣服上的数字 $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$ 为止。
  CPP

  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;