双栈排序——二分图染色的运用典型

· · 题解

让我们考虑，如果告诉每个数如果进入哪个栈，那么通过模拟就能确定序列

解释：当每个元素进哪个栈确定时，不确定的只有某个元素进一个栈，和另一个栈弹出元素的顺序。

这种情况，因为要求字典序最小，而 a 栈的所有操作的字典序都小于 b 栈，我们每次有元素进 b 栈前先尽可能把 a 栈能弹出的先弹出。

这样，我们知道，只要确定每个数进入哪个栈，问题就解决了！

怎么确定呢？？

也就是确定哪些元素无论是否同时在栈内，都不能进入同一个栈。即，找到所有 i 元素选择进入 a 栈，那么 j 元素只能进入 b 栈的情况。

如果有一个顺序靠前的元素，和一个顺序靠后的元素，前者大于后者，前者和后者可以进入同一个栈，即前面的元素进入没有弹出时，后面的元素进入。

如果有一个顺序靠前的元素 i，和一个顺序靠后的元素 j，前者大小小于后者：

提醒：这里 i,j 指下标

1.前者和后者可以进入同一个栈，即前面的元素 i 进入后弹出了，后面的元素 j 再进入，前提是 i 可以做到在 j 加入前弹出。

2.什么时候前提不成立？在 j 的后面还有个元素，比 i 元素的大小还要小，那 i 在 j 加入前就没办法弹出，如果弹出了 (a_i>a_k) 就不是升序，那 j 就不能和 i 进入同一个栈。

通过后缀最小值处理这个复杂度在 O(n^2)

谁和谁矛盾判断出来了，那么矛盾的每一对进行建边，跑二分图染色，如果能成功染色，就是一个可行方案。

#include<bits/stdc++.h>
using namespace std;
int n;
const int N=1010;
vector<int>G[N];
int a[N],sa[N];
int col[N];//1 进a 2 进b
vector<int>stuc[3];//栈。手写或者用 stack 也行，不过我没用习惯。
bool dfs(int x,int c)
{
    col[x]=c;
    for(int i=0;i<G[x].size();i++)
    {
        int j=G[x][i];
        if(col[j]==c)return 0;
        if(col[j]==0)
        if(!dfs(j,c%2+1))return 0;
    }
    return 1;
}
inline void solve(){
    cin>>n;
    sa[n+1]=114514;//任意大于 1000 的数
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=n;i>=1;i--)
        sa[i]=min(sa[i+1],a[i]);
    for(int i=1;i<=n;i++)
    for(int j=i+1;j<=n;j++)
        if(a[i]<a[j]&&sa[j]<a[i])
            G[i].push_back(j),G[j].push_back(i);
    for(int i=1;i<=n;i++)
    if((!col[i])&&(!dfs(i,1))){cout<<0<<endl;return;}
    //给没染过的每个点跑染色
    //下面，进行模拟
    int s=1;//辅助变量，表示已经弹出了值为 [1,s) 的数，即该弹 s 了
    for(int i=1;i<=n;i++)
    {
        int t=col[i];
        while(stuc[t].size()&&*(stuc[t].end()-1)<a[i])//*(stuc[t].end()-1) 表示取尾元素的值
            if(*(stuc[1].end()-1)==s)
                stuc[1].pop_back(),cout<<"b ",s++;
            else stuc[2].pop_back(),cout<<"d ",s++;
        if(t==2)
            while(stuc[1].size()&&*(stuc[1].end()-1)==s)
                stuc[1].pop_back(),cout<<"b ",s++;
        stuc[t].push_back(a[i]),
        cout<<(t==1?"a ":"c ");
    }
    while(s<=n)
    {
        while(stuc[1].size()&&*(stuc[1].end()-1)==s)
            stuc[1].pop_back(),cout<<"b ",s++;
        while(stuc[2].size()&&*(stuc[2].end()-1)==s)
            stuc[2].pop_back(),cout<<"d ",s++;
    }
}

int main()
{
    solve();
    const int _=0;
    return ~~(0^_^0);
}