题解：CF911E Stack Sorting
yushihan123
·
·
题解
首先我们要知道栈的性质是先进后出，然后我们先来模拟一下进出栈的过程。
例如，a 数组中的数分别为 a_{1},a_{2}...,a_{k},...a_{n}，并且 a_{k}=1，那我们可以把 a_{1} 到 a_{k} 放入栈 s，这时栈顶元素是 a_{k}，也就是 1，我们就可以弹出 a_{k}，放入 b 数组的末尾，接下来要放 2 了，不难发现，如果 2 的位置在 a_{k} 的后面，我们只需要像前面一样把 a_{k+1} 到 2 之间的元素入栈，然后弹出 2 就可以，然后就是 2 在 a_{k} 前面的情况。
我们可以分成两类，第一种是 a_{k-1}=2，那么就是弹出 1 后，直接弹出 2 就可以。第二种是 2 在 a_{k-1} 之前，如果想要弹出 2，就必须弹出 2 到 a_{k-1}，之间的数，但是如果弹出的话，那么在 b 数组中 2 前面就会有比 2 大的数，就不合法了可以直接输出 -1。
总结一下就是：在给出的前 k 个元素中，如果 a_{i} 的左边有比 a_{i} 小的元素，并且这个元素比 a_{i} 右边的某个元素大的话，就可以直接输出 -1 了。
用不等式可以表示成：j<i<k 并且 a_{k}<a_{j}<a_{i}。
还有一种需要输出 $-1$ 的情况，可以参考样例 $4$，就是构造出来的 $a_{k}$ 后面的数，不满足上面总结的性质，具体可以看代码 $39$ 和 $40$ 行，我们需要找到 $x$ 没有在前 $k$ 个数中出现过，并且 $x+1$ 在前 $k$ 个数中出现过的数，在第 $4$ 个样例中，$2$ 没有出现过，$3$ 出现过，我们就可以找 $3$ 的右边有没有比 $3$ 大的数，这里可以用单调栈维护，如果有就满足了上面总结的性质，直接输出 $-1$ 就可以。
注意：题目中要求**字典序最大**。
细节可以看代码 $44$ 到 $46$ 行，至于为什么不把不在前 $k$ 个数中的数直接倒着输出，而是要把每一段连续的数，按照区间数值的范围从小到大，把每一段的数从大到小倒着输出，可以看样例 $3$ 这个反例，因为直接倒着输出的话 $a_{k+1}$ 右边一定会有比它小的，假设这个数为 $t$，因为 $a_{k+1}$ 和 $t$ 不是连续的，所以前 $k$ 个数中一定会有数大于 $t$，就不满足性质了。
剩下大于前 $k$ 个数中最大值的数，直接倒着输出就可以。
代码如下：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int a[N],stk[N],s[N],top;
int st[N],mi[N];
set<int> se;
int main(){
int n,k,mx=0;
scanf("%d%d",&n,&k);
for(int i=1;i<=k;i++){
scanf("%d",&a[i]);
st[a[i]]=i;
mx=max(mx,a[i]);
}
mi[k+1]=0x3f3f3f3f;
for(int i=k;i>=1;i--){
mi[i]=min(mi[i+1],a[i]);
}
se.insert(a[1]);
se.insert(0);
for(int i=2;i<k;i++){
auto it=se.lower_bound(a[i]);
it--;
if(*it>mi[i+1]){
printf("-1");
return 0;
}
se.insert(a[i]);
}
for(int i=k;i>=1;i--){
while(top&&stk[top]<=a[i]) top--;
if(top==0) s[i]=0;
else s[i]=stk[top];
stk[++top]=a[i];
}
int cnt=k;
int t=1;
for(int i=1;i<=mx;i++){
if(st[i]||(!st[i]&&!st[i+1])) continue;
if(s[st[i+1]]){
printf("-1");
return 0;
}
for(int j=i;j>=t;j--){
if(!st[j]) a[++cnt]=j;
}
t=i+1;
}
for(int i=n;i>mx;i--){
if(!st[i]) a[++cnt]=i;
}
for(int i=1;i<=n;i++){
printf("%d ",a[i]);
}
return 0;
}
```