正经题解｜寻找排列

题目解析

首先思考下怎么才能让排列最小，显然对于位置 $i$ 来说 填入 $i$ 这样子填是最小的。
举一个例子，当 $n$ 为 $6$，$x$ 为 $2$，对于头与尾的数已经固定了，考虑中间的数，如果 $i$ 的位置能填 $i$ 则填 $i$。
2 6 3 4 5 1 此时我们发现 $n$ 只能填在位置 $x$ 上，如果不能填，则找不到最小排列，再考虑 $n$ 能不能交换到后面找到一个更小的排列。

AC代码

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
int t,n,m,x;
int vis[N];
int main() {
    ios::sync_with_stdio(false);
    cin >> t;
    while(t--) {
        cin >> n >> x;
        vector<int> ans;
        memset(vis,0,sizeof vis);
        vis[x] = 1;
        int flag = n % x == 0;
        if (flag) {
            ans.push_back(x);
            for(int i=2;i<n;i++) {
                if (i == x)ans.push_back(n);
                else ans.push_back(i);
            }
            ans.push_back(1);
            int j = x - 1;
            for(int i=x;i<n-1;i++) {
                if (ans[i] % (j + 1) == 0 && ans[j] % (i+1) == 0) {
                    swap(ans[j],ans[i]);
                    j = i;
                }
            }
            for(int &i:ans)cout << i << " ";
            cout << endl;
        }else {
            cout << -1 << endl;
        }
    }
    return 0;
}

复杂度

对于任意一组序列都要对后面的数进行一次判定，是否能交换到更小的排列，复杂度为 $O(n)$。