自动搬运

查看原文

来自洛谷，原作者为

	Maxmilite **

搬运于2025-08-24 21:14:55，当前版本为作者最后更新于2023-05-12 19:03:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Source & Knowledge

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

题目大意

$n$ 个编号，从左向右依次为 $a _ 1, a _ 2, \cdots, a _ n$，每次给定一个整数 $k$，将其按照 $1, k + 1, 2k + 1, \cdots, 2, k + 2, 2k + 2, \cdots$ 的方式进行排布，询问在 $T$ 次排布后从左向右的编号。

题目分析

我们使用两个数组 $f, g$，其中 $f$ 存储当前的编号顺序信息，$g$ 用于暂存。暂存的实现方法下面会讲到。

首先进行读入过程，对于 $T$ 次排布，我们每次读入整数 $k$，接下来进行排布过程。

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$。

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$ 数组即可完成任务。

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;

视频讲解