CF911E Stack Sorting题解

尹昱钦 · 2021-02-21 10:17:26 · 题解

题目理解

给你一个栈和一个序列，让你在这个序列的末尾加入剩下的元素，要求能够利用这个栈使弹出顺序符合 1\to n 的顺序。

思路

我们不难发现：

• 栈内元素清空后，剩下的元素从大到小放入答案序列尾部。
• 比栈顶元素小的元素在栈底则无解。

把给定的元素全部压入栈中，压入栈的过程中同时能弹出就弹出（要符合字典序，即从 1 开始），然后对剩下的元素进行处理——

对每一个栈顶元素 k，比 k 小的元素一定要比 k 先出栈，所以应把从 k-1 到上一个栈顶元素之间的数字放到答案序列中（倒序的目的是使答案字典序最大），最后弹出此栈顶元素。若发现这些数字有的已经在栈中了，则无解输出 -1。

清空完栈后，按照结论 1，把剩下的元素从大到小放入答案序列尾部即可。

实际上，这个栈就类似一个单调栈。

代码

#include<cstdio>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cmath>
#include<stack>
using namespace std;
const int maxn=200005;
int n,k,cnt=1; 
int vis[maxn],a[maxn];
stack<int> s;
int main(){
    cin>>n>>k;
    for(int i=1;i<=k;i++){
        scanf("%d",&a[i]);
        vis[a[i]]=1;
        s.push(a[i]);
        while(!s.empty()&&s.top()==cnt){
            cnt++;
            s.pop();
            continue;
        }
    }
    while(!s.empty()){
        for(int i=s.top()-1;i>=cnt;i--){
            if(vis[i]){
                cout<<-1;
                return 0;
            }
            a[++k]=i;
            vis[i]=1;
        }
        cnt=s.top()+1;
        s.pop();
    }
    for(int i=n;i>=cnt;i--){
        a[++k]=i;
    }
    for(int i=1;i<=n;i++){
        cout<<a[i]<<" ";
    }
    return 0;
}