[语言月赛202305] 排排队，做游戏 题解
Maxmilite
·
·
题解
Source & Knowledge
2023 年 5 月语言月赛，由洛谷网校入门计划/基础计划提供。
题目大意
## 题目分析
我们使用两个数组 $f, g$，其中 $f$ 存储当前的编号顺序信息，$g$ 用于暂存。暂存的实现方法下面会讲到。
首先进行读入过程，对于 $T$ 次排布，我们每次读入整数 $k$，接下来进行排布过程。
```cpp
const int MAXN = 10005;
int n, T;
int f[MAXN], g[MAXN];
cin >> n >> T;
for (int i = 1; i <= n; ++i)
cin >> f[i];
while (T--) {
int k;
cin >> k;
// ...
}
```
接下来，接下来使用二重循环完成排布。具体的，我们新建一个变量 `cnt`，用于指代当前已经放入了多少元素。二重循环第一重枚举 $i, k + i, 2k + i, \cdots$ 中的 $i$，第二重枚举 $k$ 前的系数。由于当 $i \gt k$ 时，$Xk + i$ 会被之前的 $(X + 1)k + (i - k)$ 等覆盖到，因此这里 $i$ 最大为 $k$。
```cpp
while (T--) {
int k;
cin >> k;
int cnt = 0;
for (int i = 1; i <= k; ++i) {
for (int j = 0; i + j * k <= n; ++j) {
int val = i + j * k;
g[++cnt] = f[val];
}
}
}
```
为了不破坏 $f$ 的完整性，这里引入了 $g$ 数组，这也是「暂存」的实现方法：不断向 $g$ 数组中塞入新的元素（`g[++cnt] = f[val];`）。
最后，用 $g$ 覆盖 $f$ 即可。最终直接输出 $f$ 数组即可完成任务。
```cpp
while (T--) {
// ...
for (int i = 1; i <= n; ++i)
f[i] = g[i];
}
for (int i = 1; i <= n; ++i)
cout << f[i] << " ";
cout << endl;
```
## 视频讲解
