题目描述 Description
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希望知道其中字典序最小的操作序列是什么。
输入描述 Input Description
输入的第一行是一个整数n。
第二行有n个用空格隔开的正整数，构成一个1~n的排列。
输出描述 Output Description
输出共一行，如果输入的排列不是“可双栈排序排列”，输出数字0；否则输出字典序最小的操作序列，每两个操作之间用空格隔开，行尾没有空格。
样例输入 Sample Input
【样例1】
4
1 3 2 4
【样例2】
4
2 3 4 1
【样例3】
3
2 3 1
样例输出 Sample Output
【样例1】
a b a a b b a b
【样例2】
0
【样例3】
a c a b b d
数据范围及提示 Data Size & Hint
30%的数据满足： n<=10
50%的数据满足： n<=50
100%的数据满足： n<=1000
/* 不得不说，真的是很神奇的一道题 自己想着是要用字典序的，所以应该按顺序考虑a,b,c,d，然而noipT4怎么可能这么简单没有考虑一种最重要的情况，当i<j<k,且ak<ai<aj时，i和j必定不能在一个栈中，这就是解题的关键，利用染色的原理，处理出哪些元素在s1中，哪些元素在s2中，然后模拟出答案。 RE了N多次，rmq还是不太熟啊！ */ #include<cstdio> #include<iostream> #include<cmath> #include<cstring> #define N 1010 using namespace std; int a[N],head[N],mn[N][25],color[N],s1[N],s2[N],n,top1,top2,cnt; bool flag; struct node { int v,pre; };node e[N*N]; void rmq() { memset(mn,127/3,sizeof(mn)); for(int i=1;i<=n;i++)mn[i][0]=a[i]; for(int j=1;j<=20;j++) for(int i=1;i+(1<<j)-1<=n;i++) mn[i][j]=min(mn[i][j-1],mn[i+(1<<j-1)][j-1]); } int query(int x,int y) { int k=log(y-x+1)/log(2); return min(mn[x][k],mn[y-(1<<k)+1][k]); } void add(int x,int y) { ++cnt; e[cnt].v=y; e[cnt].pre=head[x]; head[x]=cnt; } void dfs(int x) { if(flag)return; for(int i=head[x];i;i=e[i].pre) if(!color[e[i].v]) { color[e[i].v]=3-color[x]; dfs(e[i].v); } else if(color[e[i].v]==color[x]) { flag=true;return; } } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); rmq(); for(int i=1;i<=n;i++) for(int j=i+1;j<n;j++)//交了N多变都是RE，原因就是多写了个“=”，然后就用了log（0） { if(a[i]>a[j])continue; int x=query(j+1,n); if(x<a[i])add(a[i],a[j]),add(a[j],a[i]); } for(int i=1;i<=n;i++) if(!color[i]) { color[i]=1; dfs(i); if(flag) { printf("0"); return 0; } } int now=1; for(int i=1;i<=n;i++) { if(color[a[i]]==1) { if(a[i]==now){printf("a b ");now++;} else { while(a[i]>s1[top1]&&top1)top1--,printf("b "); s1[++top1]=a[i];printf("a "); } } else { if(a[i]==now){printf("c d ");now++;} else { while(a[i]>s2[top2]&&top2)top2--,printf("d "); while(s1[top1]==now)top1--,printf("b "),now++; s2[++top2]=a[i];printf("c "); } } } for(int i=now;i<=n;i++) { while(top1&&i==s1[top1])top1--,printf("b "); while(top2&&i==s2[top2])top2--,printf("d "); } return 0; }