C++(g++ 7.5.0) 解法, 执行用时: 254ms, 内存消耗: 20104K, 提交时间: 2023-02-23 14:14:37

#include<bits/stdc++.h>
using namespace std;
int l[3000000],r[3000000],a[1000000];
int main()
{
 	int t=1;
 	while (t--)
 	{
 		int n;
 		scanf("%d",&n);
 		for (int i=1;i<=n;i++) scanf("%d",&a[i]);
 		int len=0,ret=0;
 		for (int i=1;i<=n;)
 		{
 			//printf("%d %d\n",i,a[i]);
 			if (a[i]==i) 
			{
				i++;
			 	continue;
			}
			int tmp;
			if (i<=n/2) tmp=n;
			else tmp=1;
			if (abs(a[i]-i)>=n/2)
			{ 
				int xx=a[i]; 
				len++;
				l[len]=i,r[len]=a[i];
				swap(a[i],a[xx]);
			}
			else
			{
				//printf("%d %d %d\n",i,a[i],tmp);
				if (abs(a[i]-tmp)<n/2) 
				{
					int nex,xx=a[i];
					//printf("why %d %d\n",i,a[i]);
					if (tmp==1) nex=n;
					else nex=1;
					if (i==1) nex=2;
					len++;l[len]=i,r[len]=tmp;
					swap(a[i],a[tmp]);
					len++;l[len]=tmp,r[len]=nex;
					swap(a[tmp],a[nex]);
					len++;l[len]=nex,r[len]=xx;
					swap(a[nex],a[xx]);
					len++;l[len]=tmp,r[len]=nex;
					swap(a[tmp],a[nex]);
					len++;l[len]=i,r[len]=tmp;
					swap(a[i],a[tmp]);
				}	
				else
				{
					int xx=a[i];
					len++; l[len]=i,r[len]=tmp;
					swap(a[i],a[tmp]);
					len++; l[len]=tmp,r[len]=xx;
					swap(a[tmp],a[xx]);
					len++; l[len]=tmp,r[len]=i;
					swap(a[tmp],a[i]);
				}
			}
			//for (int i=1;i<=n;i++) printf("%d ",a[i]);
			//printf("\n");
			//if (len>100) break;
		}
		printf("0\n%d\n",len);
		for (int i=1;i<=len;i++) printf("%d %d\n",l[i],r[i]);
 	}
 	return 0;
}

C++ 解法, 执行用时: 173ms, 内存消耗: 26412K, 提交时间: 2021-12-12 13:05:24

#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
int n,m,i,j,k,x,y,t,ans[3*N],cnt,a[N],b[N],ans2[3*N];
void doit(int x,int y){if (x==y) return;
	t=a[x];a[x]=a[y];a[y]=t;b[a[x]]=x;b[a[y]]=y;ans[++cnt]=x;ans2[cnt]=y;
}
int main(){
	scanf("%d",&n);for (i=1;i<=n;i++) scanf("%d",&a[i]),b[a[i]]=i;printf("0\n");
	for (i=0;i<=n/2-1;i++){
		if (n/2-i!=a[n/2-i]){
			if (b[n/2-i]>n/2) doit(1,b[n/2-i]);
			doit(b[n/2-i],n),doit(n,n/2-i);
		}
		if (n/2+i+1!=a[n/2+i+1]){
			if (b[n/2+i+1]<=n/2) doit(b[n/2+i+1],n);
			doit(b[n/2+i+1],1);doit(1,n/2+i+1);
		}
	}
	printf("%d\n",cnt);for (i=1;i<=cnt;i++) printf("%d %d\n",ans[i],ans2[i]);return 0;
}