题目描述
Tom最近在研究一个有趣的排序问题。如图所示，通过2个栈S1和S2，Tom希望借助以下4种操作实现将输入序列升序排序。
操作a
如果输入序列不为空，将第一个元素压入栈S1
操作b
如果栈S1不为空，将S1栈顶元素弹出至输出序列
操作c
如果输入序列不为空，将第一个元素压入栈S2
操作d
如果栈S2不为空，将S2栈顶元素弹出至输出序列
如果一个1~n的排列P可以通过一系列操作使得输出序列为1，2，…，(n-1)，n，Tom就称P是一个“可双栈排序排列”。例如(1,3,2,4)就是一个“可双栈排序序列”，而(2,3,4,1)不是。下图描述了一个将(1,3,2,4)排序的操作序列： < a,c,c,b,a,d,d,b>
当然，这样的操作序列有可能有几个，对于上例(1,3,2,4)，< a,c,c,b,a,d,d,b>是另外一个可行的操作序列。Tom希望知道其中字典序最小的操作序列是什么。 输入输出格式 输入格式：
输入文件twostack.in的第一行是一个整数n。
第二行有n个用空格隔开的正整数，构成一个1~n的排列。
输出格式：
输出文件twostack.out共一行，如果输入的排列不是“可双栈排序排列”，输出数字0；否则输出字典序最小的操作序列，每两个操作之间用空格隔开，行尾没有空格。
考虑单栈排序，非法的条件是大数在小数后出现，这样小数必须先出栈，但是如果大数之后又有一个更小的数，那么小数就不能抢先出栈，这样就无解了。 所以可以预处理出哪些数不能在一个栈里，二分图染色判断合法性，然后模拟一遍就好了。
#include<cstdio> #include<cstring> #include<stack> #include<vector> using namespace std; const int oo=0x3f3f3f3f; vector<int> to[1010]; int a[1010],clr[1010],s1[1010],s2[1010]; bool dfs(int u,int x) { clr[u]=x; for (int i=0;i<to[u].size();i++) if (!clr[to[u][i]]) { if (!dfs(to[u][i],3-x)) return 0; } else { if (clr[to[u][i]]==x) return 0; } return 1; } int main() { int i,j,k,m,n,p,q,x,y,s,t1=0,t2=0,mn,now; scanf("%d",&n); for (i=1;i<=n;i++) scanf("%d",&a[i]); mn=oo; for (i=n;i;i--) { for (j=i-1;j;j--) if (a[i]>a[j]&&a[j]>mn) { to[i].push_back(j); to[j].push_back(i); } mn=min(mn,a[i]); } for (i=1;i<=n;i++) if (!clr[i]) if (!dfs(i,1)) { printf("0\n"); return 0; } p=1; now=0; for (i=1;i<=2*n;i++) { if (s1[t1]==now+1) { t1--; now++; printf("b"); } else { if (clr[p]==1&&(t1==0||a[p]<s1[t1])) { s1[++t1]=a[p]; p++; printf("a"); } else { if (s2[t2]==now+1) { t2--; now++; printf("d"); } else { s2[++t2]=a[p]; p++; printf("c"); } } } printf("%c",i==2*n?'\n':' '); } }