双栈排序

题目

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)不是。

输入格式

输入的第一行是一个整数p,代表有p组测试数据。

每组测试数据的第一行有一个正整数n,第二行有n个用空格隔开的正整数,构成一个1~n的排列。

输出格式

输出共p行,如果输入的排列不是”可双栈排序排列”,输出数字0。

否则输出字典序最小的操作序列,每两个操作之间用空格隔开,行尾没有空格。

数据范围

1≤n≤1000

输入:

1
3
2 3 1

输出:

a c a b b d 

分析

  • 模拟进栈出栈顺序,我们发现, 假如存在a[k]<a[i]<a[j] (i<j<k);
  • 那么i和j肯定不能进同一个栈,而且不满足这个条件的一定可以放入同一个栈。
  • 所以,我们要将这样i和j分别分进两个,所以就成了二分图的问题,先将二分图,染成两种颜色,然后模拟进栈顺序,相同颜色的放同一个栈即可。
  • 如果不能染成两种颜色,即无解。

代码

#include <iostream>
#include <cstring>
#include <stack>
using namespace std;
const int N=1e3+5;

int n,a[N],f[N];
bool g[N][N];
int color[N];

bool dfs(int x,int c){//染色
    color[x]=c;
    for(int i=1;i<=n;i++){
        if(g[x][i]){
            if(color[i]==c) return false;
            if(!color[i]&&!dfs(i,-c)) return false;
        }
    }
    return true;
}

int main()
{
    int t;
    cin>>t;
    while(t--){
        memset(g,0,sizeof(g));
        memset(f,0,sizeof(f));
        cin>>n;
        f[n+1]=n+1;
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=n;i>=1;i--) f[i]=min(f[i+1],a[i]);

        for(int i=1;i<=n;i++){ // a[k]<a[i]<a[j]  i<j<k 
            for(int j=i+1;j<=n;j++){ //那么ij肯定不能在同一个栈中 
                if(a[i]<a[j]&&f[j+1]<a[i]){
                    g[i][j]=g[j][i]=true;
                }
            }
        }

        bool flag=true;
        memset(color,0,sizeof(color));
        for(int i=1;i<=n;i++){//染色,并将相邻顶点染成不同颜色
            if(!color[i]&&!dfs(i,1)){
                flag=false;
                break;
            }
        }
        if(!flag){
            cout<<0<<endl;
            continue;
        }
//        for(int i=1;i<=n;i++) cout<<color[i]<<" ";

        int now=1;
        stack<int> s1,s2;
        for(int i=1;i<=n;i++){ //模拟进栈

            if(color[i]==1){
                s1.push(a[i]);
                cout<<"a ";
            }else{
                s2.push(a[i]);
                cout<<"c ";
            }

            while(true){
                if(!s1.empty()&&s1.top()==now){
                    s1.pop();
                    now++;
                    cout<<"b ";
                }else if(!s2.empty()&&s2.top()==now){
                    s2.pop();
                    now++;
                    cout<<"d ";
                }else{
                    break;
                }

            } 
        }
        cout<<endl;
    }
    return 0;
}

   转载规则


《双栈排序》 蒋曾辉 采用 知识共享署名 4.0 国际许可协议 进行许可。
 上一篇
城市游戏 城市游戏
有一天,小猫rainbow和freda来到了湘西张家界的天门山玉蟾宫,玉蟾宫宫主蓝兔盛情地款待了它们,并赐予它们一片土地。
2019-08-27
下一篇 
矩阵 矩阵
给定一个M行N列的01矩阵(只包含数字0或1的矩阵),再执行Q次询问,每次询问给出一个A行B列的01矩阵,求该矩阵是否在原矩阵中出现过。
2019-08-25
  目录