洛谷传送门

CF传送门

---

解题思路

紫题？？

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

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

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

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

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

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

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

AC代码

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<iomanip>
 5 #include<cmath>
 6 #include<stack>
 7 using namespace std;
 8 const int maxn=200005;
 9 int n,k,cnt=1; 
10 int vis[maxn],a[maxn];
11 stack<int> s;
12 int main(){
13     cin>>n>>k;
14     for(int i=1;i<=k;i++){
15         scanf("%d",&a[i]);
16         vis[a[i]]=1;
17         s.push(a[i]);
18         while(!s.empty()&&s.top()==cnt){
19             cnt++;
20             s.pop();
21             continue;
22         }
23     }
24     while(!s.empty()){
25         for(int i=s.top()-1;i>=cnt;i--){
26             if(vis[i]){
27                 cout<<-1;
28                 return 0;
29             }
30             a[++k]=i;
31             vis[i]=1;
32         }
33         cnt=s.top()+1;
34         s.pop();
35     }
36     for(int i=n;i>=cnt;i--){
37         a[++k]=i;
38     }
39     for(int i=1;i<=n;i++){
40         cout<<a[i]<<" ";
41     }
42     return 0;
43 }