双栈排序

这里提供二分图染色的解法

两个数 i,j(i≤j)i,j(i≤j) 不能被放入同一个栈中，当且仅当存在 k,k>jk,k>j, 且 q[k]<q[i]<q[j]q[k]<q[i]<q[j]。

有了上述性质后，我们只需将所有满足条件的点分到两个栈中去即可。
这一步可以转化成图论问题：如果i, j满足条件，则在i和j之间连一条边。
然后判断是否是二分图即可。

复杂度是

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp(aa,bb) make_pair(aa,bb)
#define _for(i,b) for(int i=(0);i<(b);i++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,b,a) for(int i=(b);i>=(a);i--)
#define mst(abc,bca) memset(abc,bca,sizeof abc)
#define X first
#define Y second
#define lowbit(a) (a&(-a))
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
typedef long double ld;
const int N=1010;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const double eps=1e-6;
int a[N],f[N];
vector<int> g[N];
int color[N]; //顶点颜色(1 or -1)
stack<int> s1,s2;
int n;

bool dfs(int v,int c){
    color[v]=c;
    for(int i=0;i<g[v].size();i++){
        if(color[g[v][i]]==c) return false; //相邻点同色
        if(color[g[v][i]]==0 && !dfs(g[v][i],-c)) return false; //未染色,染成-c
    }
    return true;
}

int main(){
//     ios::sync_with_stdio(0);
//     cin.tie(0);
#ifdef DEBUG
    freopen("F:/laji/1.in", "r", stdin);
//    freopen("F:/laji/2.out", "w", stdout);
#endif
    cin>>n;
    rep(i,1,n) cin>>a[i];
    f[n+1]=n+1;
    per(i,n,1) f[i]=min(f[i+1],a[i]);
    rep(i,1,n){
        rep(j,i+1,n){
            if(a[i]<a[j]&&f[j+1]<a[i]) g[i].pb(j),g[j].pb(i);
        } 
    }

    rep(i,1,n){
        if(color[i]==0 && !dfs(i,1)){
            cout<<"0\n";
            return 0;
        }
    }

    int now=1;
    rep(i,1,n){
        while((s1.size()&&s1.top()==now)||(s2.size()&&s2.top()==now)){
            if(s1.size()&&s1.top()==now){
                s1.pop();
                cout<<"b ";
            }
            else{
                if(color[i]==1) s1.push(a[i++]),cout<<"a ";
                else s2.pop(),cout<<"d ";
            }
            now++;
        }

        if(i>n) break;

        if(color[i]==1) s1.push(a[i]),cout<<"a ";
        else s2.push(a[i]),cout<<"c ";
    }

    while((s1.size()&&s1.top()==now)||(s2.size()&&s2.top()==now)){
        if(s1.size()&&s1.top()==now) s1.pop(),cout<<"b ";
        else s2.pop(),cout<<"d ";
        now++;
    }

    return 0;
}