自动搬运

查看原文

来自洛谷，原作者为

	Ecrade_ 算法竞赛打 APIO，就像，只能度过一个相对失败的人生。

搬运于2025-08-24 22:47:33，当前版本为作者最后更新于2023-05-15 21:49:04，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

一个重要的观察：将 $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;
}