来源：牛客网
@[toc]

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 131072K，其他语言262144K
64bit IO Format: %lld

题目描述

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希望知道其中字典序最小的操作序列是什么。

输入描述:
第一行是一个整数n。
第二行有n个用空格隔开的正整数，构成一个1~n的排列
输出描述:
共一行，如果输入的排列不是“可双栈排序排列”，输出数字0；否则输出字典序最小的操作序列，每两个操作之间用空格隔开，行尾没有空格。
示例1
输入
复制

4
1 3 2 4

输出
复制

a b a a b b a b

示例2
输入
复制

4
2 3 4 1

输出
复制

0

示例3
输入
复制

3
2 3 1

输出
复制

a c a b b d

备注:

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

题意：

有四种操作，问如何操作可以实现将输入序列升序排序
四种操作分别是：
操作a：如果输入序列不为空，将第一个元素压入栈S1
操作b：如果栈S1不为空，将S1栈顶元素弹出至输出序列
操作c：如果输入序列不为空，将第一个元素压入栈S2
操作d：如果栈S2不为空，将S2栈顶元素弹出至输出序列

题解：

貌似二分图可以做（不过我还没看懂）
首先推出规律：

对于任意两个数t[i]和t[j],它们不能压入同一个栈中的充要条件: 存在一个k,使得i<j<k且t[k]<t[i]<t[j]。

可以用反证法来证明
现在有两个栈，我们对两个逐次遍历，我们只需要将满足这个要求的点各自归到一边，中间连一条线，遍历结束后就得到一个图，用经典的染色法判断是否为二分图，若是则按照颜色入栈，借助染色情况进行排序
若不是则说明不能完成

代码：

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<stack>
#include<cmath>
#define maxn 1004
using namespace std;

const int inf=19260817;
int n,num;
int color[maxn];
int t[maxn];    //要排序的元素的存储
int s[maxn];    //判断两个数字是否满足规则
bool flag,e[maxn][maxn];

void paint(int x,int c){    //DFS进行染色
    color[x]=c;
    for(int i=1;i<=n;i++){
        if(e[x][i]){    //查找相邻点 
            if(color[i]==c) flag=false;        //若相邻点颜色相同，则错误
            if(!color[i]) paint(i,3-c);        //若未染过色，对其染色，3-c结果为1,2，表示1与2号栈
        }
    }
}

void make(){    //创造二分图
    s[n+1]=inf;     
    for(int i=n;i>=1;i--){
        s[i]=t[i];
        if(s[i+1]<s[i])
            s[i]=s[i+1];
    }
    for(int i=1;i<n;i++){
        for(int j=i+1;j<n;j++){
            if(t[i]<t[j] && s[j+1]<t[i]){
                e[i][j]=e[j][i]=1;  //按规则创建图
            }
        }
    }
    for(int i=1;i<=n;i++){ 
        if(!color[i]){         //染色
            paint(i,1);
        }
    }
}

void work(){
    if(flag==false){
        printf("0\n");
        return ;        
    }
    stack<int> stack1,stack2;
    int now=1;
    for(int i=1;i<=n;i++){
        if(color[i]==1){     //入栈
            stack1.push(t[i]);
            printf("a ");            
        }
        else {
            stack2.push(t[i]);
            printf("c ");               
        }
        while((!stack1.empty() && stack1.top()==now) || 
              (!stack2.empty() && stack2.top()==now)){     //判断是否弹出
            if(!stack1.empty() && stack1.top()==now){
                stack1.pop();
                now++;
                printf("b ");
            }
            else{
                stack2.pop();
                now++;
                printf("d ");                
            }
        }
    }
}

int main(){
    flag=1;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&t[i]);
    }
    make();
    work();   
    return 0;
}