[NC22669] 栈和排序

1
2
3
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 131072K，其他语言262144K
64bit IO Format: %lld

题目描述

给你一个1->n的排列和一个栈，入栈顺序给定

你要在不打乱入栈顺序的情况下，对数组进行从大到小排序

当无法完全排序时，请输出字典序最大的出栈序列

输入描述:

1
2
第一行一个数n
第二行n个数，表示入栈的顺序，用空格隔开，结尾无空格

输出描述:

1
输出一行n个数表示答案，用空格隔开，结尾无空格

示例1

输入

1
2
5
2 1 5 3 4

输出

1
5 4 3 1 2

说明

1
2入栈；1入栈；5入栈；5出栈；3入栈；4入栈；4出栈；3出栈；1出栈；2出栈

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <stack>
#include <algorithm>

using namespace std;

int p[1000010],maxn[1000010];
stack<int> st;

int main(){
    int n;
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> p[i];
    }
    for(int i=n;i>=1;i--){
        maxn[i] = max(maxn[i+1],p[i]);
    }
    for(int i=1;i<=n;i++){
        st.push(p[i]);
        while(!st.empty() && st.top() > maxn[i+1]){
            cout << st.top() << " ";
            st.pop();
        }
    }
    while(!st.empty()){
        cout << st.top() << " ";
        st.pop();
    }
    return 0;
}

代码解释

  • 首先维护了一个后缀最大值的数组,这是一个小技巧.
  • 再批量把栈顶中的数字和后缀最大值比较,如果栈顶大则弹出栈顶.

问题总结

首先把while写成了for,再是在大于号出了问题.

1
while(!st.empty() && st.top() > maxn[i+1])