CF-911E.Stack Sorting(栈)

洛谷传送门

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 }

 

上一篇:PAT A1052 Linked List Sorting


下一篇:PAT 甲级 1028 List Sorting (25分)