题目描述
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':' ');}
}