自动搬运

查看原文

来自洛谷，原作者为

	银杉水杉秃杉 原神OI堂主 QQ群853353679 详细主页在博客

搬运于2025-08-24 22:33:39，当前版本为作者最后更新于2021-09-08 09:50:46，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

虽说这次月赛比较阴间，但这道题并不是想象的那么难（虽然月赛中这T1花了我半小时QwQ）

我们需要逆向推理一下，对于一个长度为 $n$ 的排列，进行不超过 $m$ 次操作过后的最小字典序最大是什么。

对于每一次操作，肯定是把后面的最小数移到前面去，例如：第一次操作把 $1$ 放到第 $1$ 位，第二次操作把 $2$ 放到第 $2$ 位，以此类推。 最后我们经过 $m$ 次操作后，得到的排列前 $m$ 项必然为 $\{1, 2, 3, \dots, m-1, m\}$，为了使后面的字典序最大，后 $n-m$ 项必然为 $\{n, n-1, n-2, \dots, m+2, m+1\}$。 整体排列（下文称此为最终排列）为 $\{1, 2, 3, \dots, m-1, m, n, n-1, n-2, \dots, m+2, m+1\}$。 （比如：当 $n=5,m=3$ 时，最终的排列为 $\{1,2,3,5,4\}$）

现在，我们要做的就是把这个最终排列还原成 $m$ 次操作前的初始排列。 还原的方式有很多很多种（所以这道题才会是Special Judge）， 下面介绍其中两种。

第一种：由于我们会把 $1\sim m$ 移到前 $m$ 项，不如刚开始时把最终的第 $m+1$ 项也就是 $n$ 放到开头，$1\sim m$ 放在第 $2\sim m+1$ 项。 初始排列为 $\{n,1,2,3,\dots,m-1,m,n-1,n-2,\dots,m+2,m+1\}$。 需要注意的是当 $n=m$ 时，排列为 $\{n,1,2,3,\dots,n-2,n-1\}$。

第一种方法的代码如下：

#include <bits/stdc++.h>
using namespace std;
int T, n, m;
int main()
{
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d%d", &n, &m);
        printf("%d ", n);//先输出n
        for (int i = 1; i <= min(m, n - 1); i++)//min的作用是来特判n=m
            printf("%d ", i);//输出1-m
        for (int i = n - 1; i >= m + 1; i--)
            printf("%d ", i);//输出n-1到m+1
        printf("\n");//记得换行
    }
    return 0;
}

第二种：这种方法有点小玄学，是我比赛时想到的。 构造好最终排列后，我们要进行 $m$ 次交换将其还原，不如我们就一次一次交换回去。 从第 $m$ 项开始，将其与第 $n$ 项交换（也就是将 $m$ 和 $m+1$ 交换），第 $m-1$ 项与第 $n-1$ 项交换，以此类推，直至第 $1$ 项与第 $n-m+1$ 项交换，共 $m$ 次操作。

个人还是推荐用第一种方法，第二种实在不好想到。

第二种方法的代码如下：

#include <bits/stdc++.h>
using namespace std;
int T, n, m;
int a[100010];
int main()
{
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= m; i++)
            a[i] = i;
        for (int i = m + 1; i <= n; i++)//先构造最终排列
            a[n - i + m + 1] = i;
        for (int i = m; i >= 1; i--)//从m项开始一次次交换
            swap(a[i], a[n + i - m]);
        for (int i = 1; i <= n; i++)
            printf("%d ", a[i]);
        printf("\n");//记得换行
    }
    return 0;
}

如果你觉得这篇题解还不错，点个赞再走呗OwO