题目中给定两个栈对一个排列进行排序
保证字典序最小就是尽可能用第一个栈进行操作

显然每个数只会入栈和出栈一次
我们只需找到每个数会进入哪个栈即可保证有唯一的答案
尽量让前面的数属于第一个栈来保证字典序最小

本题有一个很强的性质
对于任意一对 0 < i < j < n 如果存在任一 k>j 使得a[j]>a[i]>a[k] 是 i 与 j 不能进入同一个栈 的充要条件

证明：
先证充分性：
反证法，如果i，j（ 0 < i < j < n ）进入同一个栈，且存在一　k>j 使得a[j]>a[i]>a[k]　
则如果ｊ进栈时ｉ已出栈，则之后的ｋ还未出栈，输出序列不能单增，与题意不符
如果ｊ进栈时i未出栈，则ｊ一定在ｉ之前出栈，与题意不符
所以i，j一定不能进入同一个栈
再证必要性：
也用反证法，如果i，j不能进入同一个栈，且不存在 k>j 使得a[j]>a[i]>a[k]
那么j和j之后的元素一定在i之后出栈，所以当序列遍历到j时，一定可以让i出栈，进而j就可以进栈了

证毕。

根据此性质可以找到哪些数不能在进入一个栈中，给不能进入同一个栈的数连边
利用染色法划分二分图，不是二分图输出0，是二分图根据划分的栈模拟找到答案序列

细节见代码

模拟时有一个优先级问题需要注意，在出栈前a这个操作的优先级是更高的

hack数据（单数据版）：
5
2 3 1 4 5
输出：a c a b b a d b a b

#include <iostream>
#include <stack>

using namespace std;

const int N = 1010,M = N * N,inf = 0x3f3f3f3f;

int h[N],ne[M],e[M],idx;
int a[N],n,col[N];
stack<int> s1,s2;

void add(int u,int v)
{
    ne[++ idx] = h[u];
    e[idx] = v;
    h[u] = idx;
}

bool dfs(int u,int c)
{
    col[u] = c;
    for(int i = h[u]; i ;i = ne[i])
    {
        int v = e[i];
        if(col[v] == 0 && dfs(v,3 - c) == 0)return 0;
        else if(col[v] == c)return 0;
    }
    return 1;
}

int main()
{
    cin >> n;
    for(int i = 1;i <= n;i ++)
        scanf("%d",&a[i]);
    for(int i = 1;i < n;i ++)
    {
        int minn = inf;
        for(int j = n;j > i;j --)
        {
            if(a[i] < a[j] && minn < a[i])add(i,j),add(j,i);
            minn = min(minn,a[j]);
        }
    }

    for(int i = 1;i <= n;i ++)
        if(col[i] == 0 && dfs(i,1) == 0)
        {
            puts("0");
            return 0;
        }

    int now = 1;
    printf("a ");
    s1.push(a[1]);
    for(int i = 2;i <= n;i ++)
    {
        while((s1.size() && s1.top() == now) || (s2.size() && s2.top() == now))
        {
            if(s1.size() && s1.top() == now)printf("b "),s1.pop();
            if(s2.size() && s2.top() == now)
            {
                if(col[i] == 1)printf("a "),s1.push(a[i]),i ++;
                printf("d "),s2.pop();
            }
            now ++;
        }

        if(i > n)break;

        if(col[i] == 1)printf("a "),s1.push(a[i]);
        else printf("c "),s2.push(a[i]);
    }

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

作者：羽笙
链接：https://www.acwing.com/activity/content/code/content/81016/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。