「RHOI-1」似曾相识燕归来 题解

· · 题解

一个重要的观察：将 1 调整到首位之后，其余元素可以任意交换位置。

令 q 为 p 的逆，记 f(p) 为 p 的置换环个数。

一个经典的结论：对于一个 1\sim n 的排列 p，一次操作可以交换其中任意两个数的位置，则至少需要 n−f(p) 次操作才能将 p 升序排列，因为每次交换最多使 f(p) 减少 1。一种可行的交换方案是，从小到大枚举 i，若 p_i\neq i，则交换 p_i 和 p_{q_i}。

接下来考虑如何在将 1 用尽量少的操作次数调整到首位的同时，使 f(p) 尽量大。

下面默认第 (i+1) 个 Case 不包含第 1\sim i 个 Case。

Case 1： n\le 3

特判即可。

Case 2： q_1=n

容易发现这种情况下我们无法移动 1 的位置，故输出 -1。

Case 3： q_1=1

容易发现这种情况下我们可以利用 1 交换排列中除了 1 的任意两个数，故此时交换的最少次数为 n-f(p)\le n。

Case 4： \exists \ q_1<i\le n,p_i<p_1

进行一次 (1,q_1,i) 的操作即可转换为 Case 3，容易发现总最少操作次数仍为 n-f(p)\le n。

Case 5： p_1\ge 3

由于 1 右边的数均比 p_1 大，故 1 左边一定存在一个 i\ (2\le i<q_1) 使得 p_i<p_1，进行一次 (1,i,n) 的操作即可转换为 Case 4。由于两次操作后 p_1=1，故操作次数 \le 2+(n-2)=n。

Case 6： p_1=2,p_2=1,p_i=i\ (3\le i\le n)

此种情况下的最少操作次数为 5 次，一种可行的方案为 (1,2,3),(1,2,3),(1,2,4),(1,3,4),(1,2,4)。注意此时若 n=L=4 需输出 -1。

Case 7： p_1=2,p_2=1

找到一个 i\ (3\le i<n) 满足 p_i>p_{i+1}，则我们可以进行 (1,2,i),(1,2,i),(1,i,i+1) 三次操作使得 p_1=1,p_2=2，故操作次数 \le 3+(n-3)=n。

Case 8：p_1=2

若 q_n=2，进行 (1,2,q_1),(1,q_1,n) 两次操作，否则进行 (1,2,q_n),(1,2,q_1),(1,q_1,n) 三次操作，由于至多三次操作后 p_1=1,p_2=2，故操作次数 \le 3+(n-3)=n。

时间复杂度为 O(\sum n)。

#include<bits/stdc++.h>
using namespace std;
int t,n,l,cnt,p[2000009],q[2000009];
struct st{int x,y,z;}ans[2000009];
inline int read(){
    int s = 0,w = 1;
    char ch = getchar();
    while (ch > '9' || ch < '0'){ if (ch == '-') w = -1; ch = getchar();}
    while (ch <= '9' && ch >= '0') s = (s << 1) + (s << 3) + (ch ^ 48),ch = getchar();
    return s * w;
}
void print(){
    if (cnt > l){puts("-1"); return;}
    printf("%d\n",cnt);
    for (int i = 1;i <= cnt;i += 1){
        printf("%d %d %d\n",ans[i].x,ans[i].y,ans[i].z);
    }
}
void add(int x,int y,int z){
    if (p[x] > p[z]) swap(p[x],p[y]),swap(q[p[x]],q[p[y]]);
    else swap(p[y],p[z]),swap(q[p[y]],q[p[z]]);
    ans[++ cnt] = (st){x,y,z};
}
void swapsort(){
    for (int i = 1;i <= n;i += 1) if (q[i] != i) add(1,min(i,q[i]),max(i,q[i]));
}
void work(){
    if (n == 1) return;
    if (q[1] == n){cnt = 1e9; return;}
    if (n == 2) return;
    if (q[1] == 1){swapsort(); return;}
    if (n == 3){
        if (p[1] == 2) cnt = 1e9;
        else add(1,2,3),add(1,2,3);
        return;
    }
    int pos = q[1];
    for (int i = pos + 1;i <= n;i += 1) if (p[i] < p[1]){
        add(1,pos,i),swapsort();
        return;
    }
    if (p[1] >= 3){
        for (int i = 2;i < pos;i += 1) if (p[i] < p[1]){
            add(1,i,n),add(1,pos,n),swapsort();
            return;
        }
        return;
    }
    if (p[2] == 1){
        for (int i = 3;i < n;i += 1) if (p[i] > p[i + 1]){
            add(1,2,i),add(1,2,i),add(1,i,i + 1),swapsort();
            return;
        }
        add(1,2,3),add(1,2,3),add(1,2,4),add(1,3,4),add(1,2,4);
        return;
    }
    if (q[n] > 2) add(1,2,q[n]);
    add(1,2,pos),add(1,pos,n),swapsort();
}
int main(){
    t = read();
    while (t --){
        n = read(),l = read(),cnt = 0;
        for (int i = 1;i <= n;i += 1) p[i] = read();
        for (int i = 1;i <= n;i += 1) q[p[i]] = i;
        work(),print();
    }
    return 0;
}