P1155 双栈排序

双栈排序

洛谷链接

用双栈进行排序，也就是给出一个序列，让你用两个栈来排序，输出排序的操作类型。

实现也比较简单，如果存在一个k,使得i<j<k且a[k]<a[i]<a[j]，那么i和j就不能存在一个栈中。

代码：

#include<cstdio>
#include<cstdlib>
#include<stack>
#define N 420000
using namespace std;
int head[N],next[N],to[N],rs[N],n,a[N],f[N],num;
stack<int> s1,s2;
void add(int x,int y){
    next[++num]=head[x];
    to[num]=y;
    head[x]=num;
}
int dfs(int x,int c){
    rs[x]=c;
    for(int y,i=head[x];i;i=next[i]){
        y=to[i];
        if(rs[y]==rs[x]){
            printf("0");
            exit(0);
        }
        if(!rs[y])
            dfs(y,-c);
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    f[n+1]=N;
    for(int i=n;i>=1;i--)f[i]=min(f[i+1],a[i]);
    for(int i=1;i<n;i++)
      for(int j=i+1;j<=n;j++){
          if(a[i]<a[j]&&f[j+1]<a[i]){
              add(i,j);
              add(j,i);
          }
      }
    for(int i=1;i<=n;++i){
        if(!rs[i]){
            dfs(i,1);
        }
    }
    int aim=1;
    for(int i=1;i<=n;i++){
        if(rs[i]==1){
            printf("a ");
            s1.push(a[i]);
        }
        else{
            printf("c ");
            s2.push(a[i]);
        }
        while((!s1.empty()&&s1.top()==aim)||(!s2.empty()&&s2.top()==aim)){
            if(!s1.empty()&&s1.top()==aim){
                s1.pop();
                printf("b ");
                aim++;
            }
            else{
                s2.pop();
                printf("d ");
                aim++;
            }
        }
    }
    return 0;
}