NOIP 2008 双栈排序

大家好，欢迎来到IT知识分享网。

题目描述

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

输入输出格式

输入格式：

输入文件twostack.in的第一行是一个整数n。

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

输出格式：

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

看到这道题，首先就打了个30分的错误代码 然后又是一个30分的超时，紧接着还是30分。这道题是一道不错的题，是关于二分图的（其实看了题解很久才明白）

题解中说的很详细，但是染色的过程是比较纠结的。其实是挺有技巧的。

题解地址:http://blog.csdn.net/kqzxcmh/article/details/9566813

代码上半部分是我的龟速染色，下面才是正确的染色方法。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <stack> 
#define INF 2000100
using namespace std;
int map[1001][1001]; //0可以 1不可以 
int num[1002],dp[1002];
int col[1002]={0};
int n;
int min(int a,int b)
{
    return a>b?b:a;
}
stack<int> s1;
stack<int> s2;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",&num[i]);
    num[n+1]=INF;dp[n+1]=INF;
    for (int i=n;i>=1;--i) dp[i]=min(dp[i+1],num[i]);
    for (int i=1;i<n;++i)
        for (int j=i+1;j<=n;++j)
            if (num[i]<num[j]&&num[i]>dp[j+1])
                map[i][j]=map[j][i]=1;
    for (int i=1;i<=n;++i){
        if (col[i]==0){
            col[i]=1;
            for (int j=i+1;j<=n;j++){
                if (map[i][j]&&col[j]==1){
                    cout<<"0"<<endl;
                    return 0;
                }
                else if (map[i][j]) col[j]=2;
            }
        }
        if (col[i]==2){
            for (int j=i+1;j<=n;j++){
                if (map[i][j]&&col[j]==2){
                    cout<<"0"<<endl;
                    return 0;
                } 
            }
        }
    }
    int aim=1;
    for (int i=1;i<=n;i++){
        if (col[i]==1){
            cout<<"a ";
            s1.push(num[i]);
        }
        if (col[i]==2){
            cout<<"c ";
            s2.push(num[i]);
        }
        while (!s1.empty()){
            if (s1.top()==aim){
                aim++;
                cout<<"b ";
                s1.pop();
            }
            else break;
        }
        while (!s2.empty()){
            if (s2.top()==aim){
                aim++;
                cout<<"d ";
                s2.pop();
            }
            else break;
        }
    }
    while (!s1.empty()||!s2.empty())
    {    
        while (!s1.empty()){
            if (s1.top()==aim){
                aim++;
                cout<<"b ";
                s1.pop();
            }
            else break;
        }
        while (!s2.empty()){
            if (s2.top()==aim){
                aim++;
                cout<<"d ";
                s2.pop();
            }
            else break;
        }
    }
    cout<<endl;
}
















#include <cstdio>
#include <cstring>
#include <iostream>
#include <stack>
#include <cstdlib>
#define INF 2000100
using namespace std;
int map[1001][1001]; //0可以 1不可以 
int num[1002],dp[1002];
int col[1002]={0};
int n;
int min(int a,int b)
{
    return a>b?b:a;
}
void  dfs(int x, int c)
{
      col[x] = c;
      for (int i=1;i<=n;++i)
      if (map[x][i])
      {
          if (col[i]==c){
                cout<<"0"<<endl;
                exit(0);
        }
          if (!col[i])
             dfs(i, 3-c);
      }
}

stack<int> s1;
stack<int> s2;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",&num[i]);
    num[n+1]=INF;dp[n+1]=INF;
    for (int i=n;i>=1;--i) dp[i]=min(dp[i+1],num[i]);
    for (int i=1;i<n;++i)
        for (int j=i+1;j<=n;++j)
            if (num[i]<num[j]&&num[i]>dp[j+1])
                map[i][j]=map[j][i]=1;
    for (int i = 1; i <= n;++i)  
       if (!col[i]) dfs(i,1);
    int aim=1;
    for (int i=1;i<=n;i++){
        if (col[i]==1){
            cout<<"a ";
            s1.push(num[i]);
        }
        else {
            cout<<"c ";
            s2.push(num[i]);
        }
        while (!s1.empty()){
            if (s1.top()==aim){
                aim++;
                cout<<"b ";
                s1.pop();
            }
            else break;
        }
        while (!s2.empty()){
            if (s2.top()==aim){
                aim++;
                cout<<"d ";
                s2.pop();
            }
            else break;
        }
    }
    while (!s1.empty()||!s2.empty())
    {    
        while (!s1.empty()){
            if (s1.top()==aim){
                aim++;
                cout<<"b ";
                s1.pop();
            }
            else break;
        }
        while (!s2.empty()){
            if (s2.top()==aim){
                aim++;
                cout<<"d ";
                s2.pop();
            }
            else break;
        }
    }
    cout<<endl;
}