来源：牛客网

文章目录

时间限制：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栈顶元素弹出至输出序列

题解：

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

如果两个数 i,j(i≤j)i,j(i≤j) 不能被放入同一个栈中，当且仅当存在 k,k>jk,k>j, 且 q[k]<q[i]<q[j]q[k]<q[i]<q[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;
}