好久没写递归了，怕手生再来练练手。
题意：车轨上有上图所示的n个中转栈，现有2个列车，给出列车初始编号序列。列车从最右边驶入车轨，并且列车只能从右向左移动，要求给出列车中转操作序列，使列车经过这n个中转栈后从最左端输出时满足1~2的排列。
分析：其实这不就是火车出栈问题吗，可以用分治递归的思路，首先使一半有序，然后再合并使整体有序。
思路：具体来讲就是，一段无序的序列（编号1~2），通过一个中转栈使1 ~ 2在整个序列的前面2+1 ~ 2在整个序列的后面；再经过下一中转栈时，又能进一步进行排序，这样在最后一个中转栈是就只是两两之间的有序无序问题了。
什么都不如例子来的好使，比如n=3时，初始序列为 2 1 5 8 7 3 6 4
经过栈1时，使序列满足如下形式：2 1 3 4 | 6 7 8 5
经过栈2时，使序列满足如下形式：2 1 | 3 4 | 6 5 | 8 7
经过栈3时，使序列满足如下形式：1 2 | 3 4 | 5 6 | 7 8
然后就达到要求了。
那么该如何操作才能达到上述状态呢？
比如经过栈1时，可将序列分成包含（1~4）和（5~8）的两段子序列。那么每来一个数，判断该数是否大于4，若小于等于4，则该列车进栈接着出栈；否则该列车暂时停放在栈中，等所有小于等于4的列车出栈后再按照先进后出的性质出栈，这样就达到了目的；
经过栈1时的操作序列：2 2 1 1 5 8 7 3 3 6 4 4 6 7 8 5
经过下面的栈的情况就类似了，不再赘述了。
附代码：
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <stack>
using namespace std;
const int maxn = ;
int a[maxn];
void dfs(int num[], int r, int k)
{
if(k <= ) return ;
int s1[k/ + ];
int s2[k/ + ];
int k1 = , k2 = k/;
int l = r-k;
int mid = (l + r)/; stack<int> si;
int p1, p2; p1 = p2 = ;
for(int i = ; i < k; i++)
{
if(num[i] <= mid)
{
s1[p1++] = num[i];
printf("%d %d ", num[i], num[i]);
}
else
{
printf("%d ", num[i]);
si.push(num[i]);
}
}
while(!si.empty())
{
s2[p2] = si.top();
printf("%d ", s2[p2++]);
si.pop();
}
dfs(s1, mid, k/);
dfs(s2, r, k/);
return ;
} int main()
{
int n;
while(~scanf("%d", &n) && n)
{
int m = <<n;
for(int i = ; i < m; i++)
scanf("%d", &a[i]);
dfs(a, m, m);
printf("\n");
}
return ;
}