P1155 双栈排序

· · 个人记录

题目大意：

通过两个栈，四种操作，实现一个输入序列的升序排序

操作a: 如果输入序列不为空，将第一个元素压入栈S_1

操作b: 如果栈S_1不为空，将S_1栈顶元素弹出至输出序列

操作c: 如果输入序列不为空，将第一个元素压入栈S_2

操作d: 如果栈S_2不为空，将S_2栈顶元素弹出至输出序列

要求输出一个字符串，即操作顺序。若有多种操作，输出字典序最小的情况；若输入序列无法进行双栈排序，则输出0

思路：

通过贪心的思路可以很快的解答这个问题。 由于要求输出字典序最小的情况，所以操作应该遵循 “S_1优先” 的原则。由于栈是先入后出的数据结构，所以我们要保证栈中的数从底到顶是降序排序，这样才可以保证在弹出是总是小的数先弹出。当栈顶的数与当前待处理的数是连续数的时候，则优先考虑可以形成连续数的情况。

代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<stack>
using namespace std;
stack<int> s1,s2;
int n,a[1005],cur=1,l=1;
//cur是现在需要的数
//l相当于一个指针，用于调用目前没有处理的数中最前面的数
string output;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    //因为要输出最小字典序的结果，所以所有的操作都是s1优先于s2
    while(cur<=n){
        if(!s1.empty()&&s1.top()==cur){
            //若s1顶为所需数，弹出
            s1.pop();
            output+="b ";
            cur++;
        }
        else if(!s2.empty()&&s2.top()==cur){
            //若s2顶为所需数，弹出
            s2.pop();
            output+="d ";
            cur++;
        }
        else if(a[l]==cur){
            //若待当前为所需数，则压入s1后立即弹出
            output+="a b ";
            cur++,l++;
        }
        else if(!s1.empty()&&s1.top()==a[l]+1){
            //若s1顶为下一个所需数，则将当前数压入s1
            s1.push(a[l]);
            output+="a ";
            l++;
        }
        else if(!s2.empty()&&s2.top()==a[l]+1){
            //若s2顶为下一个所需数，则将当前数压入s2
            s2.push(a[l]);
            output+="c ";
            l++;
        }
        else if(s1.empty()||s1.top()>a[l]){
            //若s1为空或s1顶大于待当前数，则将当前数压入s1
            s1.push(a[l]);
            output+="a ";
            l++;
        }
        else if(s2.empty()||s2.top()>a[l]){
            //若s2为空或s2顶大于待当前数，则将当前数压入s2
            s2.push(a[l]);
            output+="c ";
            l++;
        }
        else{
            //若以上所有操作都无法进行，则无法进行双栈排序
            printf("0\n");
            return 0;
        }
    }
    cout<<output<<endl;
    return 0;
}