1170 双栈排序
2008年NOIP全国联赛提高组
时间限制: 1 s
空间限制: 128000 KB
题目描述 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
/* 对于一个栈 给一个序列可以很容易判断按规定输出 现在有如下性质 当存在i<j<k并且a[k]<a[i]<a[j] 在a[k]出栈之前a[i]和a[j]不能出栈 而a[i]比a[j]先来 但要先出不符合栈的性质 所以a[i],a[j]肯定不在一个栈中 当出现a,b,c都不在同一个栈那么不能实现双栈排序 输出0 标记好后只需看1和2两个栈怎么进出即可 注意字典序 又一遍打错RMQ QAQ...... */ #include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<stack> #define maxn 1010 using namespace std; int n,topt,flag; int a[maxn],color[maxn]; int first[maxn]; int f[maxn][15]; struct edge { int to; int next; }e[maxn*maxn*2]; stack<int>A,B; void add(int x,int y) { topt++; e[topt].to=y; e[topt].next=first[x]; first[x]=topt; } void prepare() { for(int j=1;j<=12;j++) for(int i=1;i+(1<<j)-1<=n;i++) f[i][j]=min(f[i][j-1],f[i+(1<<j-1)][j-1]); } int query(int l,int r) { int k=log(r-l+1)/log(2); return min(f[l][k],f[r-(1<<k)+1][k]); } void dfs(int x,int p) { int t; if(p==1) t=2; else t=1; if(color[x]&&color[x]!=p){flag=1;return;} if(color[x])return; color[x]=p; for(int i=first[x];i;i=e[i].next) { int to=e[i].to; dfs(to,t); if(flag)return; } } int main() { freopen("twostack.in","r",stdin); freopen("twostack.out","w",stdout); scanf("%d",&n); memset(f,127/3,sizeof(f)); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); f[i][0]=a[i]; } prepare(); for(int i=1;i<n;i++) { for(int j=i+1;j<n;j++) { int r=query(j+1,n); if(r<a[i]&&a[i]<a[j]) add(i,j),add(j,i); } } for(int i=1;i<=n;i++) { if(!color[i]) { dfs(i,1); if(flag)break; } } if(flag){printf("0 ");return 0;} int now=1; for(int i=1;i<=n;i++) { if(color[i]==2) { B.push(a[i]); printf("c "); while((!B.empty()&&B.top()==now)||(!A.empty()&&A.top()==now)) { if(!B.empty()&&B.top()==now) { B.pop();now++; printf("d "); } if(!A.empty()&&A.top()==now) { A.pop();now++; printf("b "); } } } else { A.push(a[i]); printf("a "); while((!B.empty()&&B.top()==now)||(!A.empty()&&A.top()==now)) { if(!B.empty()&&B.top()==now) { B.pop();now++; printf("d "); } if(!A.empty()&&A.top()==now) { A.pop();now++; printf("b "); } } } } return 0; }