luogu1155 双栈排序

luogu1155 双栈排序

​​ 题目描述

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)排序的操作序列：

#include#include#include#define inf 0x7f7f7f7f#define N 1100using namespace std;inline char gc(){ static char now[1<<16], *S, *T; if(S==T){T=(S=now)+fread(now, 1, 1<<16, stdin); if(S==T)return EOF;} return *S++;}inline int read(){ int x=0;char ch=gc(); while (ch<'0'||ch>'9') ch=gc(); while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=gc();} return x;}int color[N];int h[N],s1[N],s2[N],a[N],min1[N],num,n;struct node{ int y,next;}data[N*N*2];inline void insert1(int x,int y){ data[++num].y=y;data[num].next=h[x];h[x]=num; data[++num].y=x;data[num].next=h[y];h[y]=num;}bool dfs(int x,int colour){ color[x]=colour; for (int i=h[x];i;i=data[i].next){ int y=data[i].y;if (color[y]==color[x]) return false; if (color[y]!=-1) continue;if (!dfs(y,colour^1)) return false; } return true;}int main(){ freopen("1155.in","r",stdin); n=read(); for (int i=1;i<=n;++i) a[i]=read();min1[n+1]=inf; for (int i=n;i>=1;--i) min1[i]=min(a[i],min1[i+1]); for (int i=1;i<=n;++i) for (int j=i+1;j<=n;++j) if (a[i]

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。