CF-911E.Stack Sorting（栈）

洛谷传送门

CF传送门

---

解题思路

紫题？？

洛谷的题目颜色真的太准！

读完题，我们可以发现以下结论：

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

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

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

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

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

AC代码

#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;
}