双栈排序
【问题描述】
Tom 最近在研究一个有趣的排序问题。如图所示,通过 2 个栈 S1 和 S2,Tom 希望借助以下 4 种操作实现将输入序列升序排序。

操作 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;
否则输出字典序最小的操作序列,每两个操作之间用空格隔开,行尾没有空格。
【输入输出样例 1】

【输入输出样例 2】

【输入输出样例 3】

【限制】
30%的数据满足: n<=10
50%的数据满足: n<=50
100%的数据满足: n<=1000
查看答案与解析
答案:<p style="text-align: left;">#include <bits/stdc++.h></p><p style="text-align: left;">using namespace std;</p><p> </p><p style="text-align: left;">const int Max=1010;</p><p style="text-align: left;">int n,m=1,size,tot1,tot2,p1[Max],p2[Max];</p><p style="text-align: left;">int first[Max],f[Max],num[Max],vis[Max];</p><p style="text-align: left;">struct shu{int to,next,len;}edge[Max*Max];</p><p> </p><p style="text-align: left;">inline int get_int()</p><p style="text-align: left;">{</p><p style="text-align: left;"><span style="white-space:pre"> </span>int x=0,f=1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>char c;</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(c=getchar();(!isdigit(c))&&(c!='-');c=getchar());</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(c=='-') f=-1,c=getchar();</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+c-'0';</p><p style="text-align: left;"><span style="white-space:pre"> </span>return x*f;</p><p style="text-align: left;">}</p><p> </p><p style="text-align: left;">inline void build(int x,int y)</p><p style="text-align: left;">{</p><p style="text-align: left;"><span style="white-space:pre"> </span>edge[++size].next=first[x],first[x]=size,edge[size].to=y;</p><p style="text-align: left;"><span style="white-space:pre"> </span>edge[++size].next=first[y],first[y]=size,edge[size].to=x;</p><p style="text-align: left;">}</p><p> </p><p style="text-align: left;">inline void pre()</p><p style="text-align: left;">{</p><p style="text-align: left;"><span style="white-space:pre"> </span>f[n]=num[n];</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i=n-1;i>=1;i--) f[i]=min(f[i+1],num[i]);</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i=1;i<=n;i++)</p><p style="text-align: left;"><span style="white-space:pre"> </span> for(int j=i+1;j<=n;j++)</p><p style="text-align: left;"><span style="white-space:pre"> </span> if(f[j]<num[i]&&num[i]<num[j]) build(i,j);</p><p style="text-align: left;">}</p><p> </p><p style="text-align: left;">inline bool dfs(int p,int color)</p><p style="text-align: left;">{</p><p style="text-align: left;"><span style="white-space:pre"> </span>vis[p]=color;</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int u=first[p];u;u=edge[u].next)</p><p style="text-align: left;"><span style="white-space:pre"> </span>{</p><p style="text-align: left;"><span style="white-space:pre"> </span> int to=edge[u].to;</p><p style="text-align: left;"><span style="white-space:pre"> </span> if(!vis[to]) dfs(to,3-color);</p><p style="text-align: left;"><span style="white-space:pre"> </span> else if(color==vis[to]) return 0;</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>return 1;</p><p style="text-align: left;">}</p><p> </p><p style="text-align: left;">int main()</p><p style="text-align: left;">{</p><p style="text-align: left;"><span style="white-space:pre"> </span>n=get_int();</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i=1;i<=n;i++) num[i]=get_int();</p><p style="text-align: left;"><span style="white-space:pre"> </span>pre();</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i=1;i<=n;i++) if(!vis[i]&&!dfs(i,1)) {puts("0");return 0;}</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i=1;i<=n;i++)</p><p style="text-align: left;"><span style="white-space:pre"> </span>{</p><p style="text-align: left;"><span style="white-space:pre"> </span> if(vis[i]==1)p1[++tot1]=num[i],printf("a ");</p><p style="text-align: left;"><span style="white-space:pre"> </span> else p2[++tot2]=num[i],printf("c ");</p><p style="text-align: left;"><span style="white-space:pre"> </span> while(m==p1[tot1]||m==p2[tot2])</p><p style="text-align: left;"><span style="white-space:pre"> </span> {</p><p style="text-align: left;"><span style="white-space:pre"> </span> <span style="white-space:pre"> </span>if(m==p1[tot1]) tot1--,printf("b ");</p><p style="text-align: left;"><span style="white-space:pre"> </span> <span style="white-space:pre"> </span>else tot2--,printf("d ");</p><p style="text-align: left;"><span style="white-space:pre"> </span> <span style="white-space:pre"> </span>m++;</p><p style="text-align: left;"><span style="white-space:pre"> </span> }</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>return 0;</p><p style="text-align: left;">}</p>
这道题暂未补解析。