Description：

有两个栈，每次可以把序列中的下一个数压入栈一，压入栈二，弹出栈一栈顶，弹出栈二栈顶，判断一个排列能否通过这些操作升序排序，并输出字典序最小的方案。

$1\le n \le 1000$

Solution：

两个数 $a[i],a[j]$ 不能被压入同一个栈中的充要条件是存在一个 $a[k]$ 满足 $i<j<k$ 且 $a[k]<a[i]<a[j]$ ，于是就记一个后缀最小值，每次枚举两个数判断能否合法，如果他们两个不能被压入同一个栈中，那就连一条无向边，那么可双栈排序当且仅当这个图是二分图，于是二分图判定即可，最后输出方案直接模拟注意各个操作的先后顺序，记一个光标表示当前输出到什么位置，如果应该弹栈了，就不能给这个栈压栈，注意弹栈栈不为空，压栈 $i\le n$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<stack>

#include<cstring>

using namespace std;

int n;

#define MAXN 1010

#define INF 0x3f3f3f3f

int a[MAXN],suf_min[MAXN];

struct edge

{

    int to,nxt;

}e[MAXN * MAXN * 2];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

    ++edgenum;e[edgenum].to = b;e[edgenum].nxt = lin[a];lin[a] = edgenum;

    ++edgenum;e[edgenum].to = a;e[edgenum].nxt = lin[b];lin[b] = edgenum;

    return;

}

bool vis[MAXN];

bool tag[MAXN];

stack<int> s1,s2;

bool dfs(int k)

{

    vis[k] = true;

    for(int i = lin[k];i != 0;i = e[i].nxt)

    {

        if(vis[e[i].to])

        {

            if(tag[e[i].to] == tag[k])return false;

            continue;

        }

        tag[e[i].to] = tag[k] ^ 1;

        dfs(e[i].to);

    }

    return true;

}

int main()

{

    scanf("%d",&n);

    for(int i = 1;i <= n;++i)scanf("%d",&a[i]);

    suf_min[n + 1] = n + 1;

    for(int i = n;i >= 1;--i)suf_min[i] = min(suf_min[i + 1],a[i]);

    for(int i = 1;i < n;++i)

        for(int j = i + 1;j <= n;++j)

            if(a[i] < a[j])

                if(suf_min[j + 1] < a[i])add(i,j);

    for(int i = 1;i <= n;++i)

    {

        if(!vis[i])

        {

            if(!dfs(i))

            {

                puts("0");

                return 0;

            }

        }

    } 

    for(int i = 1,j = 1;i <= n || !s1.empty() || !s2.empty();)

    {

        if(!s1.empty() && s1.top() == j)

        {

            putchar('b'),putchar(' ');

            s1.pop();

            ++j;

            continue;

        }

        if(i <= n && tag[i] == 0)

        {

            putchar('a');putchar(' ');

            s1.push(a[i]);

            ++i;

            continue;

        }

        if(!s2.empty() && s2.top() == j)

        {

            putchar('d');putchar(' ');

            s2.pop();

            ++j;

            continue;

        }

        if(i <= n && tag[i] == 1)

        {

            putchar('c');putchar(' ');

            s2.push(a[i]);

            ++i;

            continue;

        }

    }

    puts("");

    return 0;

}