双栈排序

题意：
给你一个长度为n的序列，你是否能用两个栈用以下操作进行排序？
操作a：如果输入序列不为空，将第一个元素压入栈S1
操作b：如果栈S1不为空，将S1栈顶元素弹出至输出序列
操作c：如果输入序列不为空，将第一个元素压入栈S2
操作d：如果栈S2不为空，将S2栈顶元素弹出至输出序列
不能输出0，能则输出最小字典序的操作。

思路：
对每一个数进行处理时能放入第一个栈就不放第二个栈，这样就能确保得到的是最小字典序的操作。
什么时候可以放入第一个栈呢，就是该数后面的第一个大于它并且不能放入第二个栈的数的后面的数没有一个数比它小，既在遇到这个数时该数已经输出了。

代码：

#include <bits/stdc++.h>
typedef long long ll;

using namespace std;

const ll inf=998244353;

inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

string s;
int a[1005], n, ma[1005];

int main()
{
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&a[i]);
    }
    stack<int> st1, st2;
    int flag=1, q=1;
    for(int i=1; i<=n; i++)
    {
        if(!st1.empty()&&a[i]>st1.top())
        {
            if(st2.empty()||a[i]<st2.top())
            {
                s.push_back('c');
                ma[a[i]]=1;
                st2.push(a[i]);
            }
            else
            {
                flag=0;
                break;
            }

        }
        else
        {
            int p=1;
            int ka=i+1;
            for(; ka<=n; ka++)
            {
                if(a[ka]>a[i]&&!st2.empty()&&st2.top()<a[ka])
                {
                    break;
                }
            }
            for(ka; ka<=n; ka++)
            {
                if(a[ka]<a[i])
                {
                    p=0;
                    break;
                }
            }
            if(p)
            {
                s.push_back('a');
                ma[a[i]]=1;
                st1.push(a[i]);
            }
            else if(st2.empty()||a[i]<st2.top())
            {
                s.push_back('c');
                ma[a[i]]=1;
                st2.push(a[i]);
            }
            else
            {
                flag=0;
                break;
            }
        }
        while((!st1.empty()&&st1.top()==q)||(!st2.empty()&&st2.top()==q))
        {
            if(!st1.empty()&&st1.top()==q)
            {
                s.push_back('b');
                st1.pop();
            }
            else
            {
                s.push_back('d');
                st2.pop();
            }
            q++;
        }
    }
    if(flag==0)
    {
        printf("0\n");
    }
    else
    {
        for(int i=0; i<s.length(); i++)
        {
            printf("%c%c",s[i],i+1==s.length()?'\n':' ');
        }
    }
    return 0;
}