双栈排序 noip2008

首先可以看出第一个栈和第二个栈是没什么交集的，那么第一步是对这些元素分别归到两个栈里，

当存在k使i<j<k,a[k]<a[i]<a[j]时，i，j是不能放在一个栈里的，需要一种数据结构表示这种关系，建成图，用二分图的方法判断一下，尽量放到第一个栈里面；

然后就是模拟一下；

自己写无从下手，只好看别人题解后发上来；

 #include<iostream>

 #include<cstdio>

 #include<string>

 #include<cstring>

 #include<algorithm>

 #include<iomanip>

 #include<cstdlib>

 #include<stack>

 using namespace std;

 const int maxn=+,inf=;

 int n,a[maxn],ma[maxn][maxn],f[maxn],color[maxn];

 void NO_ANSWER(){

     printf("");

     exit();

 }

 int x[maxn],y[maxn],topx=,topy=;

 void dfs(int x,int c){

     color[x]=c;

     for(int i=;i<=n;i++){

         if(ma[x][i]){

             if(!color[i])dfs(i,-c);

             else if(color[i]==c)NO_ANSWER();

         }

     }

 }

 void init(){

     scanf("%d",&n);

     for(int i=;i<=n;i++)scanf("%d",&a[i]);

     f[n+]=inf;

     for(int i=n;i>=;i--)f[i]=min(f[i+],a[i]);

     for(int i=;i<=n;i++)

         for(int j=i+;j<=n;j++)

             if(a[i]<a[j]&&f[j+]<a[i])

                 ma[i][j]=ma[j][i]=;

     for(int i=;i<=n;i++)if(!color[i])dfs(i,);

 }

 void work(){

     int now=;

     for(int i=;i<=n;i++){

         if(color[i]==){

             x[++topx]=a[i];

             printf("a ");

         }

         else {

             y[++topy]=a[i];

             printf("c ");

         }

         while((topx&&x[topx]==now)||(topy&&y[topy]==now)){

             if(topx&&x[topx]==now){

                 topx--;printf("b ");

             }

             else {topy--;printf("d ");}

             now++;

         }

     }

 }

 int main(){

     freopen("1.in","r",stdin);

     freopen("1.out","w",stdout);

     init();

     work();

     return ;

 }

因为看别人代码写的，所以比较类似。

巴特西

双栈排序 noip2008

最新文章

热门文章