自动搬运

查看原文

来自洛谷，原作者为

	Lemansky 私だよ

搬运于2025-08-24 22:25:53，当前版本为作者最后更新于2024-08-08 13:47:55，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题意

翻译其实蛮清楚了，每次选择一段区间，将其前半部分与后半部分直接交换，从而把序列从小到大排序。构造一个操作序列即可。

这里补充一下原题面的点：序列是个 $1$ 到 $n$ 的排列。

思路

对于每组数据：

• 考虑一种贪心的暴力操作方法：把 $1$ 到 $n$ 从小到大依次归位（$a_i=i$），其合理性在于后面对右边数的操作不会影响左边已归位的数。

• 如果当前把 $i$ 归位，尽可能优的方法是选区间 $[i,pos_i]$，$pos_i$ 是 $i$ 当前的位置，这样每次就能向终点前进大约一半。

• 举个例子，序列是 $\{4,3,2,1\}$，先操作 $[1,4]$ 变为 $\{2,1,4,3\}$，再操作 $[1,2]$ 变为 $\{1,2,4,3\}$。这样 $1$ 就归位了，恰好 $2$ 也归位，再操作 $[3,4]$ 即可。

• 但是注意操作序列中的区间长度必须是偶数，因此需要微调区间的选择（即 $[i+1,pos_i]$）。

具体可以见代码。

复杂度和操作分析

对于每组数据：

• 注意到每次归位一个数大约需要 $\log n$ 次操作（每次归一半），因此估计最坏也就 $n\log n$ 次操作，$n\le 10^4$ 对于题目的限制来说完全够用了。

• 至于时间复杂度，SPJ 能跑过去那我们肯定可以每次归位最多产生 $n$ 次单位交换，暴力最坏是 $O(n^2)$ 的复杂度，但其实远远到不了，直接操作就过了。

注意本题的多测限制。

Code

#include<bits/stdc++.h>
using namespace std;
int t,n,m,a[10005],b[10005];//b数组存位置
int s,l[114514],r[114514];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>t;
	while(t--){
		cin>>n,m=1,s=0;
		for(int i=1;i<=n;++i) cin>>a[i],b[a[i]]=i;
		while(1){
			while(b[m]==m) ++m;
			if(m>n) break;
			while(b[m]!=m){//还没归位
				++s,l[s]=m+(b[m]-m+1)%2,r[s]=b[m];
				int w=(l[s]+r[s])/2;
				for(int i=l[s];i<=w;++i){
					swap(a[i],a[i+w-l[s]+1]);
					swap(b[a[i]],b[a[i+w-l[s]+1]]);
				}
			}
		}
		cout<<s<<'\n';
		for(int i=1;i<=s;++i) cout<<l[i]<<' '<<r[i]<<'\n';
	}
    return 0;
}