noip2008 雙棧排序 （二分圖染色）

P1605雙棧排序

​​Accepted​​

标簽：

​​圖結構 二分圖​​​

​​​NOIP提高組2008​​

描述

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

樣例輸入1[複制]

4

1 3 2 4

樣例輸出1[複制]

a b a a b b a b

限制

1s

提示

30%的資料滿足： n<=10

50%的資料滿足： n<=50

100%的資料滿足： n<=1000

NOIP2008 提高組第4題

解析：如果存在 a[k]<a[i]<a[j] (i<j<k)，那麼a[i]與a[j]就不能放進同一個棧中。據此，進行染色，對每個數字a[i]，記錄不能與它在同一個棧中的數字。

         用b[j]記錄[j,n]區間内的最小值，則：b[j]=min(a[j],b[j+1])，上訴不等式轉換為：b[j+1]<a[i]<a[j]。

        接下來，就是枚舉a[i]，如果a[i]能放入一号棧，則放入；否則，放入二号棧。如果a[i]是目前應當輸出的數，則輸出a[i]。

代碼：

#include<cstdio>
#include<algorithm>
#define maxn 1000
using namespace std;

int n,q[maxn+20];
int f[maxn+20],b[maxn+20];
int a[maxn+20][maxn+20];
int s1[maxn+20],s2[maxn+20];
int sum1=0,sum2=0;
char s3[maxn*1000+20];

bool dfs(int x)
{
  int i,j,k;
  for(i=1;i<=a[x][0];i++)
    {
      if(f[a[x][i]]==f[x])return 0;
      if(f[a[x][i]]==0)
      {
        f[a[x][i]]=3-f[x];
        dfs(a[x][i]);
    }
    }
  return 1;  
}

int main()
{
  int i,j,k;
  scanf("%d",&n);
  for(i=1;i<=n;i++)scanf("%d",&q[i]);
  for(b[n]=q[n],i=n-1;i>=1;i--)b[i]=min(q[i],b[i+1]);
  
  for(i=1;i<n;i++)
    for(j=i+1;j<n;j++)
      if(q[i]<q[j] && b[j+1]<q[i])
      {
        a[i][++a[i][0]]=j;
          a[j][++a[j][0]]=i;
    }
    
  for(i=1;i<=n;i++)
    {
      if(f[i]==0)f[i]=1;
      if(!dfs(i))
        {
          printf("0\n");
          return 0;
        }
    }
  
  for(i=1;i<=n;i++)
    {
      if(f[i]==1)
        { 
          s1[++s1[0]]=q[i];
          s3[++sum1]='a';
        }
      else 
      {
        s2[++s2[0]]=q[i];
        s3[++sum1]='c';
      }
    while(1)
      {
        if(s1[s1[0]]==sum2+1)
          {
            s3[++sum1]='b',sum2++,s1[0]--;
            continue;
          }
        if(s2[s2[0]]==sum2+1)
        {
          s3[++sum1]='d',sum2++,s2[0]--;
          continue;
        }
      break;    
      }  
    }
  for(i=1;i<sum1;i++)printf("%c ",s3[i]);
  printf("%c\n",s3[sum1]); 
  return 0;
}