题目地址：
https://www.acwing.com/problem/content/description/155/
Tom最近在研究一个有趣的排序问题。通过2 22个栈S1和S2，Tom希望借助以下4 44种操作实现将输入序列升序排序。
- 操作a：如果输入序列不为空，将第一个元素压入栈 S1
- 操作b：如果栈S1不为空，将S1栈顶元素弹出至输出序列
- 操作c：如果输入序列不为空，将第一个元素压入栈S2
- 操作d：如果栈S2不为空，将S2栈顶元素弹出至输出序列
如果一个1 ∼ n 1∼n1∼n的排列P PP可以通过一系列操作使得输出序列为1 , 2 , … , ( n − 1 ) , n 1,2,…,(n−1),n1,2,…,(n−1),n，Tom就称P PP是一个”可双栈排序排列”。例如( 1 , 3 , 2 , 4 ) (1,3,2,4)(1,3,2,4)就是一个”可双栈排序序列”，而( 2 , 3 , 4 , 1 ) (2,3,4,1)(2,3,4,1)不是。下图描述了一个将( 1 , 3 , 2 , 4 ) (1,3,2,4)(1,3,2,4)排序的操作序列：<a, c, c, b, a, d, d, b>
当然，这样的操作序列有可能有几个，对于上例( 1 , 3 , 2 , 4 ) (1,3,2,4)(1,3,2,4)，<a, c, c, b, a, d, d, b>是另外一个可行的操作序列。Tom希望知道其中字典序最小的操作序列是什么。
输入格式：
第一行是一个整数n nn。
第二行有n nn个用空格隔开的正整数，构成一个1 ∼ n 1∼n1∼n的排列。
输出格式：
输出共一行，如果输入的排列不是”可双栈排序排列”，输出数字0 00。
否则输出字典序最小的操作序列，每两个操作之间用空格隔开，行尾没有空格。
数据范围：
1 ≤ n ≤ 1000 1≤n≤10001≤n≤1000
如果某个1 ∼ n 1\sim n1∼n的序列q qq是一个栈序列，那么栈的操作可以如下进行：遍历序列，先将元素q [ i ] q[i]q[i]入栈，每次入栈完检查一下q [ i + 1 : ] q[i+1:]q[i+1:]是不是都比q [ i ] q[i]q[i]大，如果是，则pop。
关于栈序列，有一个定理：
一个序列是栈序列，当且仅当对于任意i < j i<ji<j，不存在k > j k>jk>j使得q [ k ] < q [ i ] < q [ j ] q[k]<q[i]<q[j]q[k]<q[i]<q[j]。
证明：
必要性：如果存在i < j < k i<j<ki<j<k使得q [ k ] < q [ i ] < q [ j ] q[k]<q[i]<q[j]q[k]<q[i]<q[j]，由于i , j i,ji,j之后都存在一个更小的q [ k ] q[k]q[k]，说明遍历到k kk之前，i , j i,ji,j都不能出栈，但是栈底到栈顶必须时刻都是单调下降的，这就矛盾了。
充分性：我们可以证明上面的模拟是可以进行的。假设某个时刻，我们要入栈q [ j ] q[j]q[j]，如果此时栈空，当然可以进行；如果栈不空，我们可以证明栈内的元素都大于q [ j ] q[j]q[j]，如果不然，找到最大的i < j i<ji<j使得q [ i ] < q [ j ] q[i]<q[j]q[i]<q[j]，由于不存在k > j , q [ k ] < q [ i ] k>j,q[k]<q[i]k>j,q[k]<q[i]，按照操作q [ i ] q[i]q[i]应该已经出栈了，就矛盾了。所以每次入栈的时候，入栈的元素一定小于栈内所有元素，而判断出栈的时刻可以用上面说的方式，从而整个过程可以顺利进行。
根据这个性质，由于两个栈相对独立，各自操作，所以我们可以将这个序列分为两部分，如果两个点不能在同一个栈中，我们就连一条边，如此做成一个无向图，如果这个图不是二分图，说明不存在划分方式，直接输出0 00，否则说明存在划分。我们用染色的方式，通过S1操作的元素染色为0 00，其余染色为1 11。
接下来求操作序列。由于要求字典序最小，我们按照能a就a，能b就b，以此类推的方式来操作。假设遇到了x = a [ j ] x=a[j]x=a[j]，同时维护一个变量，记录下一个要pop的数y yy。
- 当x xx颜色为0 00，并且要么栈1为空，要么栈1的顶大于x xx，则x xx可以入栈1，执行a；
- 当栈1的顶等于y yy，执行b；
- 当x xx颜色为1 11，并且要么栈2空，要么栈2的顶大于x xx，则x xx可以入栈2，执行c；
- 当栈2的顶等于y yy，执行d。
代码如下：
#include<algorithm>#include<cstring>#include<iostream>#include<stack>usingnamespacestd;constintN=1010;intn;inta[N],f[N];intcol[N];boolg[N][N];booldfs(intu,intc){col[u]=c;for(inti=1;i<=n;i++)if(g[u][i]){if(c==col[i])returnfalse;if(!~col[i]&&!dfs(i,!c))returnfalse;}returntrue;}intmain(){memset(g,0,sizeofg);scanf("%d",&n);for(inti=1;i<=n;i++)scanf("%d",&a[i]);f[n+1]=n+1;for(inti=n;i;i--)f[i]=min(a[i],f[i+1]);for(inti=1;i<=n;i++)for(intj=i+1;j<=n;j++)if(a[i]<a[j]&&f[j+1]<a[i])g[i][j]=g[j][i]=true;memset(col,-1,sizeofcol);boolflag=true;for(inti=1;i<=n;i++)if(!~col[i]&&!dfs(i,0)){flag=false;break;}if(!flag){puts("0");return0;}string res;stack<int>stk1,stk2;intcur=1;intj=1;for(inti=1;i<=2*n;i++){if(j<=n&&!col[j]&&(stk1.empty()||stk1.top()>a[j])){stk1.push(a[j]);j++;printf("a ");}elseif(stk1.size()&&stk1.top()==cur){stk1.pop();printf("b ");cur++;}elseif(j<=n&&col[j]&&(stk2.empty()||stk2.top()>a[j])){stk2.push(a[j]);j++;printf("c ");}elseif(stk2.size()&&stk2.top()==cur){stk2.pop();printf("d ");cur++;}}}时间复杂度O ( n 2 ) O(n^2)O(n2)，空间O ( n ) O(n)O(n)。
){kind=spacer}
