题解：P1155 [NOIP 2008 提高组] 双栈排序

· · 题解

题目大意

给出

n

个正整数的排列，问是否能够通过两个栈的进栈或出栈，实现出栈序列的单调递增，若可以给出字典序最小的方案。

思路

我们通过模拟可以得知：

第一：若一个数一直在一个栈里，则后来的数要想要进入这个栈，就必须比它小，除非这个数已然出栈。

第二：若想达到最优解，第一个元素必然放在第一个栈。

我看到这题的第一反应就是贪心：对于每个数，如果在上述条件的制约下还能放入第一个栈中，那么就直接将它放在第一个栈；如果不行，就尝试第二个栈；若还不行，则无解。于是我们就可以写出这样的代码。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,a,cnt=1;
bool flag;
stack<int>p1,p2;
queue<char>out;
signed main(){
    cin>>n;
    while(n--){
        cin>>a;
        if(p1.empty()||p1.top()>a){
            out.push('a');
            p1.push(a);
        }else if(p2.empty()||p2.top()>a){
            out.push('c');
            p2.push(a);
        }else{
            cout<<0;
            return 0;
        }
        flag=1;
        while(flag){
            flag=0;
            if(!p1.empty()&&p1.top()==cnt){
                ++cnt,flag=1;
                out.push('b');
                p1.pop();
            }
            if(!p2.empty()&&p2.top()==cnt){
                ++cnt,flag=1;
                out.push('d');
                p2.pop();
            }
        }
    }
    while(!out.empty()){
        cout<<out.front()<<' ';
        out.pop();
    }
    return 0;
}

毫无疑问地错了，仅有

30

分。原因在于这样的贪心只考虑前面的数对它的制约，而无视它对后面的数的制约。

举个例子：

7
5 7 2 4 1 6 3

代码输出无解，但这个序列是有解的，关键在于把

2

放在第二个栈而非贪心的第一个。

我们再广度思考一下：对于任何一个元素，它前面比它大的数，必然还未出栈，那么它们必然受上面规则的制约。而前面比它小的数，有可能已经出栈了，故我们先不拿上述规则制约。

那么这个规则（若一个数一直在一个栈里，则后来的数要想要进入这个栈，就必须比它小，除非这个数已然出栈）该怎么用呢？我们可以用二分图染色的思想，将两种栈抽象成二分图的左右部点，若有两个元素互相被制约，则给它们连边，表示它们不能在同一个栈中。连好边后，在用染色法时若出现染色失败，则代表无解。

按照这个想法，我们可以在每个数前面的序列中，判断任意比它大的两个数是否有制约关系并判断是否连边。

但是如果朴素地判断，时间复杂度还是

$O(n^2)

了。

染完色后，我们就从前往后遍历。若与它染色的点被遍历过了，则它进的栈的种类显然；否则，它就在第一个栈里。

最后要注意的是各个操作的字典序，经调整细节我们就能通过了。

下面贴上代码。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,a[1010],las=1;
int col[1010],cnt=1;
bool vis[1010];
struct step{
    int val,id;
}st[1010];
bool cmp(step x,step y){
    return x.val<y.val;
}
vector<int>p[1010];
stack<int>s1,s2;
bool give_color(int x){
    vis[x]=1;
    for(int i=0;i<p[x].size();i++){
        int y=p[x][i];
        if(col[y]==col[x])return 0;
        col[y]=1-col[x];
        if(!vis[y])give_color(y);
    }
    return 1;
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        st[i].id=i,st[i].val=a[i];
    }
    sort(st+1,st+1+n,cmp);
    for(int l=1;l<=n;l++){
        int i=st[l].id;
        for(int j=i-1;j>=las;j--){//las就是优化
            for(int k=j-1;k>=0;k--){
                if(a[j]<a[i]||a[k]<a[i])continue;
                if(a[k]<a[j]){
                    p[j].push_back(k);
                    p[k].push_back(j);
                }
            }
        }
        las=i;
    }
    memset(col,-1,sizeof(col));
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            col[i]=1;
            if(!give_color(i)){
                cout<<0;
                return 0;
            }
        }
    }
    for(int i=1;i<=n;i++){
        if(col[i]==1){
            s1.push(a[i]);
            cout<<"a"<<' ';
        }
        if(col[i]==0){
            s2.push(a[i]);
            cout<<"c"<<' ';
        }
        bool flag=1;
        while(flag){
            flag=0;
            if(i<=n&&col[i+1]==1&&(s1.empty()||s1.top()>a[i+1]))
                break;
            if(!s1.empty()&&s1.top()==cnt){
                s1.pop();
                ++cnt,flag=1;
                cout<<"b"<<' ';
            }
            if(i<=n&&col[i+1]==1&&(s1.empty()||s1.top()>a[i+1]))
                break;
            if(!s2.empty()&&s2.top()==cnt){
                s2.pop();
                ++cnt,flag=1;
                cout<<"d"<<' ';
            }
        }
    }
    return 0;
}

不得不说，确实毒瘤。