题解 P7852 「EZEC-9」Yet Another Easy Problem

· · 题解

虽说这次月赛比较阴间，但这道题并不是想象的那么难（虽然月赛中这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