P1155 双栈排序

题目描述

Tom最近在研究一个有趣的排序问题。如图所示，通过

操作

如果输入序列不为空，将第一个元素压入栈

操作

如果栈

操作

如果输入序列不为空，将第一个元素压入栈

操作

如果栈

如果一个

当然，这样的操作序列有可能有几个，对于上例

输入输出格式

输入格式：

第一行是一个整数

第二行有

输出格式：

共一行，如果输入的排列不是“可双栈排序排列”，输出数字

输入输出样例

输入样例#1：

4
1 3 2 4

输出样例#1：

a b a a b b a b

输入样例#2：

4
2 3 4 1

输出样例#2：

输入样例#3：

3
2 3 1

输出样例#3：

a c a b b d

说明

Solution：

　　本题二分图染色+栈模拟。　　

　　若我们知道每个数应该放在哪个栈中，就可以去模拟了。

　　考虑数$a_i,a_j,a_k$不能在同一栈的情况，若$i<j<k,a_i<a_j,a_i>a_k$那么$i,k$是肯定不能在同一栈内的，我们对二元组建边，那么就是个二分图染色的模型了。

　　由于要字典序最小，所以每次染色时另当前未被染色的位置为栈1再去dfs，染色后每个位置所在的栈就确定了。

　　然后就是纯模拟咯。

　　（安利一个神奇的调试技巧：用iostream库下的cerr代替cout，在评测机测试时会直接跳过这条输出语句，但在终端可以输出，这样就能防止忘记删调试语句而写挂！>.^_^.<）

代码：

/*Code by 520 -- 9.5*/
#include<bits/stdc++.h>
#define il inline
#define ll long long
#define RE register
#define For(i,a,b) for(RE int (i)=(a);(i)<=(b);(i)++)
#define Bor(i,a,b) for(RE int (i)=(b);(i)>=(a);(i)--)
using namespace std;
const int N=1005;
int n,a[N],minn[N],col[N];
int to[N],net[N],h[N],cnt;
int stk1[N],stk2[N],top1,top2;

il void add(int u,int v){to[++cnt]=v,net[cnt]=h[u],h[u]=cnt;}

bool dfs(int u){
    for(RE int i=h[u];i;i=net[i])
        if(!col[to[i]]) {
            col[to[i]]=col[u]^1;
            if(!dfs(to[i]))return 0;
        }
        else if(col[to[i]]==col[u]) return 0;
    return 1;
}

int main(){
    ios::sync_with_stdio(0);
    cin>>n,minn[n+1]=0x7fffffff;
    For(i,1,n) cin>>a[i];
    Bor(i,1,n) minn[i]=min(minn[i+1],a[i]);
    For(i,1,n) For(j,i+1,n) if(a[i]>minn[j+1]&&a[i]<a[j]) add(i,j),add(j,i);
    For(i,1,n) if(!col[i]) {
        col[i]=2;
        if(!dfs(i))cout<<0,exit(0);
    }
    For(i,1,n) cerr<<col[i]<<' ';cerr<<endl;
    int cnt=1;
    For(i,1,n){ 
        if(col[i]==2) stk1[++top1]=a[i],cout<<"a ";
        else stk2[++top2]=a[i],cout<<"c ";
        while(top1&&stk1[top1]==cnt||top2&&stk2[top2]==cnt){
            if(stk1[top1]==cnt) cout<<"b ",--top1;
            else cout<<"d ",--top2;
            ++cnt;
        }
    }
    return 0;
}