【每日一题】8月7日题目精讲—双栈排序

#include <bits/stdc++.h>
using namespace std;
int a[100005];
vector<int> ans;
vector<char> now;
stack<int> x,y;int cnt=1;
int n;bool flag;
bool check(int pos){
    if(y.empty()) return true;
    int i;
    for(i=pos+1;i<=n;i++) if(a[i]>a[pos]&&a[i]>y.top()) break;
    for(int j=i+1;j<=n;j++) if(a[j]<a[pos]) return false;
    return true;
}
void solve(){
	for(int i=1;i<=n*2;i++){
        flag=false;
        if((x.empty()||x.top()>a[cnt])&&cnt<=n&&check(cnt)){
            x.push(a[cnt]);
            flag=true;
            cnt++;
            now.push_back('a');
        }
        else if(!x.empty()&&ans.back()+1==x.top()){
            ans.push_back(x.top());
            x.pop();
            flag=true;
            now.push_back('b');
        }
        else if((y.empty()||y.top()>a[cnt])&&cnt<=n){
            y.push(a[cnt]);
            flag=true;
            cnt++;
            now.push_back('c');
        }
        else if(!y.empty()&&ans.back()+1==y.top()){
            ans.push_back(y.top());
            y.pop();
            flag=true;
            now.push_back('d');
        }
        if(!flag) break;
        } 
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    cnt=1;
    ans.push_back(0);
    solve();
    if(!flag) cout<<0<<endl;
    else for(auto it : now) cout<<it<<" ";
    return 0;

}