题目大意：
给出一个1∼n1∼n的排列要求将其排序，每次能交换两个位置的数当且仅当这两个位置下标差的绝对值大于等于n2n2。要求输出一组操作数不大于5n5n的方案并保证一定有解。
先不考虑操作需要的限制条件，那么要将排列排好序只需要第ii次将ii与下标为ii的那个数调换一下即可。
现在有了限制条件显然不能直接调换，我们考虑借助别的数来完成这两个数的交换。
假设需要交换的两个位置的下标分别为xx和yy且y>xy>x。
当n2≤y−xn2≤y−x时，直接交换即可。
当x>n2x>n2时，显然x,yx,y都能和11位置交换：
1,x,y1,x,y
x,1,yx,1,y
y,1,xy,1,x
1,y,x1,y,x
当y≤n2y≤n2时，x,yx,y都能和nn位置交换，方法同上。
当x≤n2,y>n2且y−x<n2x≤n2,y>n2且y−x<n2时，显然只依靠11或nn无法完成，但11和yy能交换，xx和nn也能交换：
1,x,y,n1,x,y,n
y,x,1,ny,x,1,n
y,n,1,xy,n,1,x
x,n,1,yx,n,1,y
1,n,x,y1,n,x,y
1,y,x,n1,y,x,n
可以发现这样操作对于每个点最多需要55次操作就能使它归位，所以5n5n次操作内一定能完成。
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<cstdio>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
int n,m;
int a[300010];
int b[300010];
int ans[1500010][2];
int cnt;
void get(int x,int y)
{
ans[++cnt][0]=x,ans[cnt][1]=y;
b[a[x]]=y;
b[a[y]]=x;
swap(a[x],a[y]);
}
void solve(int x,int y)
{
if(x==y)return ;
if(x>y)swap(x,y);
if(y-x>=m)get(x,y);
else if(x>m)
{
get(1,x);
get(1,y);
get(1,x);
}
else if(y<=m)
{
get(y,n);
get(x,n);
get(y,n);
}
else
{
get(1,y);
get(x,n);
get(1,n);
get(1,y);
get(x,n);
}
}
int main()
{
scanf("%d",&n);m=n/2;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
b[a[i]]=i;
}
for(int i=1;i<=n;i++)
{
solve(i,b[i]);
}
printf("%d\n",cnt);
for(int i=1;i<=cnt;i++)
{
printf("%d %d\n",ans[i][0],ans[i][1]);
}
}
|