NOIP2008 双栈排序

题目描述 Description

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)排序的操作序列：<a,c,c,b,a,d,d,b>

当然，这样的操作序列有可能有几个，对于上例(1,3,2,4)，<a,c,c,b,a,d,d,b>是另外一个可行的操作序列。Tom希望知道其中字典序最小的操作序列是什么。

输入描述 Input Description

输入的第一行是一个整数n。

第二行有n个用空格隔开的正整数，构成一个1~n的排列。

输出描述 Output Description

输出共一行，如果输入的排列不是“可双栈排序排列”，输出数字0；否则输出字典序最小的操作序列，每两个操作之间用空格隔开，行尾没有空格。

样例输入 Sample Input

【样例1】

1 3 2 4

【样例2】

2 3 4 1

【样例3】

2 3 1

样例输出 Sample Output

【样例1】

a b a a b b a b

【样例2】

【样例3】

a c a b b d

数据范围及提示 Data Size & Hint

30%的数据满足： n<=10

50%的数据满足： n<=50

100%的数据满足： n<=1000

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
#include<stack>
#define maxn 2005
using namespace std;
int n,ord[maxn],col[maxn],ok = 1,minn[maxn];
vector<int> edge[maxn];
bool dfs(int u,int last){
    col[u] = last;
    for(int i = 0;i < edge[u].size();i++){
        int j = edge[u][i];
        if(!col[j]) dfs(j,3-last);
        else if(col[j] != 3-last){
            return false;
            ok = 0;
        }    
    }
    return true;
}
int main(){
    cin>>n;
    for(int i = 1;i <= n;i++){
        cin>>ord[i];
    }
     minn[n] = ord[n];
    for(int i = n - 1; i >= 1; i--){
        if(minn[i + 1] > ord[i]){
            minn[i] = ord[i];
        }else{
            minn[i] = minn[i + 1];
        }
    }
    for(int i = 1; i < n - 1; i++){
        for(int j = i + 1; j < n; j++){
            if(ord[i] < ord[j] && ord[i] > minn[j + 1]){
                edge[i].push_back(j);
                edge[j].push_back(i);
            }
        }
    }
    for(int i = 1;i <= n;i++){
        if(col[i]) continue;
        if(!dfs(i,1)) ok = 0;
    } 
    if(!ok){
        cout<<0;
        return 0;
    }
    stack<int> a,b;
    int i = 1;
    int j = 1;
    int last = 0;
    int output[maxn];
    while(i <= n){
        while((!a.empty() && col[j] == 1 && ord[j] < a.top()) || (a.empty() && col[j] == 1)){
            output[last++] = 'a';
            a.push(ord[j]);
            j++;
        }
        while(!a.empty() && a.top() == i){
            output[last++] = 'b';
            a.pop();
            i++;
        }
        while((!b.empty() && col[j] == 2 && ord[j] < b.top()) || (b.empty() && col[j] == 2)){
            output[last++] = 'c';
            b.push(ord[j]);
            j++;
        }
        while(!b.empty() && b.top() == i){
            output[last++] = 'd';
            b.pop();
            i++;
        }
    }
    for(i = 0; i < last; i++){
        if(i != 0){
            printf(" ");
        }
        printf("%c", output[i]);
    }
    printf("
");
    return 0;
}