题目：http://uoj.ac/problem/152
orzKPM。。。
分治，把数字是l~mid的拿出来放在一根柱子上，mid+1~r放在另一根柱子上。如此递归下去，每次递归只是改一下方向，l，r。然后只要处理r-l<=1的情况就可以了。
#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> #include <cstdlib> #include <queue> #include <cmath> #define rep(i,l,r) for (int i=l;i<=r;i++) #define down(i,l,r) for (int i=l;i>=r;i--) #define clr(x,y) memset(x,y,sizeof(x)) #define maxn 1000500 #define ll long long #define inf int(1e9) using namespace std; int ansx[maxn],ansy[maxn],a[3][maxn],N[3]; int tot; int read(){ int x=0,f=1; char ch=getchar(); while (!isdigit(ch)){ if (ch=='-') f=-1; ch=getchar();} while (isdigit(ch)) {x=x*10+ch-'0'; ch=getchar();} return x*f; } void move(int x,int y){ ansx[++tot]=x+1,ansy[tot]=y+1; a[y][++N[y]]=a[x][N[x]--]; } void dfs(int x,int l,int r,int dir){ if (l==r) return; if (r-l<=1){ if ((dir==0&&a[x][N[x]-1]<a[x][N[x]])||(dir==1&&a[x][N[x]-1]>a[x][N[x]])){ move(x,(x+1)%3); move(x,(x+2)%3); move((x+1)%3,x); move((x+2)%3,x); } return; } int mid=(l+r)/2; int y=(x+1)%3,z=(x+2)%3; rep(i,l,r) if (a[x][N[x]]<=mid) move(x,y); else move(x,z); dfs(y,l,mid,1-dir); dfs(z,mid+1,r,1-dir); if (dir==0){ down(i,r,mid+1) move(z,x); down(i,mid,l) move(y,x); } else { rep(i,l,mid) move(y,x); rep(i,mid+1,r) move(z,x); } } int main(){ int n=read(); down(i,n,1) a[0][i]=read(); N[0]=n; dfs(0,1,n,0); printf("%d ",tot); rep(i,1,tot) printf("%d %d ",ansx[i],ansy[i]); return 0; }