简答题 偏难
#23617

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

双栈排序

【问题描述】

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 &lt;bits/stdc++.h&gt;</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))&amp;&amp;(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&lt;&lt;3)+(x&lt;&lt;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&gt;=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&lt;=n;i++)</p><p style="text-align: left;"><span style="white-space:pre"> </span>  for(int j=i+1;j&lt;=n;j++)</p><p style="text-align: left;"><span style="white-space:pre"> </span>    if(f[j]&lt;num[i]&amp;&amp;num[i]&lt;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&lt;=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&lt;=n;i++) if(!vis[i]&amp;&amp;!dfs(i,1)) {puts("0");return 0;}</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i=1;i&lt;=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>
这道题暂未补解析。