双栈排序 题解

首先看要求，要用两个栈把一个数组排序成递增数组，有四种操作：
a：将元素压入第一个栈
b：将第一个栈的栈顶元素弹出
c：将元素压入第二个栈
d：将第二个栈的栈顶元素弹出
要求操作的字典序最小
如果无法排成严格的递增序列，那么就输出0
我们可以发现：
如果 $i < j < k$ 且 $a_i < a_j, a_k < a_j, a_k < a_i$ 时，那么 $a_i$ 和 $a_j$ 就不能在同一个栈里
所以可以用mina记录第i个元素到最后一个元素的最小值，然后套两层for循环，判断连边

for (int i = 1 ; i <= n - 2 ; i++ ) {
    for (int j = i + 1 ; j <= n - 1 ; j++ ) {
        if (a[i] < a[j] && mina[j + 1] < a[i]) {
            g[i].push_back(j);
            g[j].push_back(i);
        }
    }
}

然后对这个图进行二分染色，相同颜色的就在同一个栈，第一个染色的一定要在第一个栈，也就是染色为0

    queue<int> q;
    int start = 1;
    for (int i = 1 ; i <= n ; i++ ) {
        if (g[i].size()) {
            start = i;
            break;
        }
    }
    q.push(start);
    vis[start] = true;
    color[start] = 0;
    while(q.size()) {
        int f = q.front();
        q.pop();
        for (auto it : g[f]) {
            if (!vis[it]) {
                color[it] = !color[f];
                vis[it] = true;
                q.push(it);
            }
            else {
                if (color[it] == color[f]) {
                    cout << 0;
                    return;
                }
            }
        }
    }

然后就可以进行操作了，遍历所有元素：
首先如果第一个栈的栈顶是未排序的元素中最小的就出栈，直到栈顶元素不是未排序元素中最小的
然后判断染色
对于一个栈，如果栈顶元素小于$a_i$就一直弹出，直到栈顶元素大于$a_i$后再将$a_i$压入栈

最后循环弹出剩余的所有元素就行了
如果可以先弹出第一个栈的元素就先弹出第一个栈的元素，保证字典序为最小的
完整代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int n;
int a[N];
int mina[N];
vector<int> g[N];
bool vis[N];
bool color[N];
void init() {
    for (int i = 1 ; i <= n - 2 ; i++ ) {
        for (int j = i + 1 ; j <= n - 1 ; j++ ) {
            if (a[i] < a[j] && mina[j + 1] < a[i]) {
                //cout << i << ' ' << j << endl;
                g[i].push_back(j);
                g[j].push_back(i);
            }
        }
    }
}
void solve() {
    init();
    /*for (int i = 1 ; i <= n ; i++ ) {
        cout << i << ':';
        for (auto it : g[i]) cout << it << ' ';
        cout << endl;
    }
    cout << endl;
    for (int i = 1 ; i <= n ; i++ ) cout << color[i];
    cout << endl;*/
    queue<int> q;
    int start = 1;
    for (int i = 1 ; i <= n ; i++ ) {
        if (g[i].size()) {
            start = i;
            break;
        }
    }
    q.push(start);
    vis[start] = true;
    color[start] = 0;
    while(q.size()) {
        int f = q.front();
        q.pop();
        for (auto it : g[f]) {
            if (!vis[it]) {
                color[it] = !color[f];
                vis[it] = true;
                q.push(it);
            }
            else {
                if (color[it] == color[f]) {
                    cout << 0;
                    return;
                }
            }
        }
    }
    stack<int> s1, s2;
    //cout << color[3] << endl;
    int minm = 1;
    for (int i = 1 ; i <= n ; i++ ) {
        while (s1.size() && s1.top() == minm) {
            minm = s1.top() + 1;
            s1.pop();
            cout << 'b' << ' ';
        }
        if (color[i]) {
            while (s2.size() && s2.top() < a[i]) {
                cout << 'd' << ' ';
                minm = s2.top() + 1;
                s2.pop();
            }
            cout << 'c' << ' ';
            s2.push(a[i]);
        }
        else {
            while (s1.size() && s1.top() < a[i]) {
                cout << 'b' << ' ';
                minm = s1.top() + 1;
                s1.pop();
            }
            cout << 'a' << ' ';
            s1.push(a[i]);
        }
    }
    while (s1.size() || s2.size()) {
        if (s1.size() && s2.size()) {
            if (s1.top() < s2.top()) {
                cout << 'b' << ' ';
                s1.pop();
            }
            else {
                cout << 'd' << ' ';
                s2.pop();
            }
        }
        else if (s1.empty()) {
            cout << 'd' << ' ';
            s2.pop();
        }
        else {
            cout << 'b' << ' ';
            s1.pop();
        }
    }
}
int main() {
    cin >> n;
    for (int i = 1 ; i <= n ; i++ ) cin >> a[i];
    mina[n] = a[n];
    for (int i = n - 1  ; i >= 1 ; i-- ) {
        mina[i] = min(a[i], mina[i + 1]);
    }
    //for (int i = 1 ; i <= n ; i++ ) cout << mina[i] << ' ';
    //cout << endl;
    solve();
    return 0;
}