题目描述

Tom最近在研究一个有趣的排序问题。

通过2个栈S1和S2，Tom希望借助以下4种操作实现将输入序列升序排序。

操作a

如果输入序列不为空，将第一个元素压入栈S1

操作b

如果栈S1不为空，将S1栈顶元素弹出至输出序列

操作c

如果输入序列不为空，将第一个元素压入栈S2

操作d

如果栈S2不为空，将S2栈顶元素弹出至输出序列

如果一个1~n的排列P可以通过一系列操作使得输出序列为1, 2,…,(n-1), n，Tom就称P是一个”可双栈排序排列”。

例如(1, 3, 2, 4)就是一个”可双栈排序序列”，而(2, 3, 4, 1)不是。

下图描述了一个将(1, 3, 2, 4)排序的操作序列：

当然，这样的操作序列有可能有几个，对于上例(1, 3, 2, 4)，是另外一个可行的操作序列。

Tom希望知道其中字典序最小的操作序列是什么。

输入格式
输入的第一行是一个整数p，代表有p组测试数据。

每组测试数据的第一行有一个正整数n，第二行有n个用空格隔开的正整数，构成一个1~n的排列。

输出格式
输出共p行，如果输入的排列不是”可双栈排序排列”，输出数字0。

否则输出字典序最小的操作序列，每两个操作之间用空格隔开，行尾没有空格。

数据范围
$1≤n≤1000$

样例

输入样例：
1
3
2 3 1
输出样例：
a c a b b d

栈

网络上超多二分图大佬,那么蒟蒻就来一发双栈排序吧…

首先我们看题目要我们字典序最小,那么明显如果两个栈,都可以放入这个数字的话,那么我们首选就把这个数字放入A数组,否则放不了就把这个数组放入B数组

放入A数组,自然是得满足全局条件,而不是局部条件,不然就是错误的贪心了.那么什么是全局条件呢?

1. 首先我们要保障这个要压入栈的数字,必须小于我当前A数组中最小的数字,不然的话,我们到了要弹出我们需要的小数字的时候,为了弹出小数字,我们就不得不让大数字先弹出.然后输出序列就崩溃了
2. 其次也是最重要的条件也就是,如果说我要压入这个候选数字的话,那么我们就先找到一个比当前候选数字大的数,而且也大于B数组栈顶的数,这个同时满足两个条件的数字位置.找到这个位置,那么我们从这个位置后面一个位置,一直到最后面,如果有一个数字比它小,那么我们就不能压入候选数字,因为不满足最优解,因为这个数字放入B数组,显然更加完美.
3. 如果当前应该弹出数字了,那么马上弹出.

C++ 代码

//单数据版本,NOIP可AC,Acwing WA了,后来修改多组数据,我也不知道为什么WA了.
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define fir(i,a,b) for(int i=a;i<=b;i++)
const int N=1110;
int n,a[N],b[N],t[N],cnt=0;
char ans[N<<1];
bool flg = 1;
bool check(int x, int bi)
{
    if(!bi)//没有数字
        return 1;
    int i;
    for(i=x+1; i<=n; i++)
        if(t[i]>t[x] && t[i]>b[bi])
            break;
    fir(j,i+1,n)
    if(t[j]<t[x])
        return 0;
    return 1;
}

int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    fir(i,1,n)
    cin>>t[i];
    a[0]=b[0]=INF;
    int ai=0,bi=0,ti=1,num=1;
    cnt=0;
    flg=1;
    fir(i,1,(n<<1))//2*N,是因为压入一次,还要弹出一次
    {
        if(a[ai] == num)//A数组栈顶应该弹出了
        {
            ai--;
            num++;
            ans[++cnt] = 'b';
        }
        else if(b[bi] == num)//B数组栈顶应该弹出了
        {
            bi--;
            num++;
            ans[++cnt] = 'd';
        }
        else if(ti<=n && t[ti]<a[ai] && check(ti, bi))//都满足了
        {
            a[++ai]=t[ti++];
            ans[++cnt]='a';//放入A数组
        }
        else if(ti<=n && t[ti]<b[bi])//A数组无法放入,那么B数组看能不能放入
        {
            b[++bi]=t[ti++];
            ans[++cnt]='c';
        }
        else//都无法放入,说明无法排序
        {
            flg=0;
            break;
        }
    }
    if(!flg)
        puts("0");
    else
    {
        fir(i,1,cnt)
        printf("%c ",ans[i]);
        puts("");
    }
    return 0;
}