题解：CF911E Stack Sorting

fish_love_cat · 2025-07-18 10:02:26 · 题解

duel 被萝卜喵打爆了 /ll

手速太慢导致的，我怎么这么菜 /ll /ll /ll

给出了一部分，可以模拟栈排序。

如果到了自己填的时候栈非空，我们对于每一个栈顶递减的向下输出直到能够模拟升序排序。

这些输出显然是必需的，降序只是为了保证字典序要求。

如果说我们需要的数字在栈里，那么一定无解。

做完了。

#include<bits/stdc++.h>
using namespace std;
int a[200005];
stack<int>st;
int need=1;
map<int,bool>mp;
vector<int>ret;
int main(){
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=k;i++){
        cin>>a[i];
        mp[a[i]]=1;
        st.push(a[i]);
        while(!st.empty()&&st.top()==need)
            st.pop(),need++;
    }
    if(st.empty()){
        for(int i=1;i<=k;i++)
            cout<<a[i]<<' ';
        for(int i=n;i>=need;i--)
            cout<<i<<' ';
        return 0;
    }
    for(int i=1;i<=k;i++)
        ret.push_back(a[i]);
    while(!st.empty()){
        for(int i=need;i<st.top();i++)
            if(mp[i]){
                puts("-1");
                return 0;
            }
        for(int i=st.top()-1;i>=need;i--)
            ret.push_back(i);
        need=st.top()+1;
        st.pop();
    }
    for(int i=n;i>=need;i--)
        ret.push_back(i);
    for(int i=0;i<n;i++)cout<<ret[i]<<' ';
    return 0;
}

Accepted.