input:stack.in output:stack.out

时间限制: 1000 ms 空间限制: 524288 KB

题目描述

输入

输出

样例输入

1
2
5
1 4 3 5 2

样例输出

1
1 2 4 3 5

数据范围限制

提示

依次使用操作 1、2、1、1、1、1、2、3、3、2 可以得到样例输出 1 2 4 3 5 。

代码

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
32
33
34
#include<bits/stdc++.h>
using namespace std;
int main()
{
    freopen("stack.in","r",stdin);
    freopen("stack.out","w",stdout);
    int n,a[110000],rm[110000],q[110000],l=1,r=0;
    scanf("%d",&n);
    rm[n+1]=100010;
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    for(int i=n;i;--i)
        rm[i]=min(rm[i+1],a[i]);
    for(int i=1;i<=n;++i){
        if(l<=r){
            if(a[q[l]]>rm[i]&&a[q[r]]>rm[i]){
                q[++r]=i;
                continue;
         }
    while(!(a[q[l]]>rm[i]&&a[q[r]]>rm[i])&&l<=r)
        if(a[q[l]]<a[q[r]])
            printf("%d ",a[q[l++]]);
        else
            printf("%d ",a[q[r--]]);q[++r]=i;
        }else{
             q[++r]=i;
        }
}
    while(l<=r)
        if(a[q[l]]<a[q[r]])
            printf("%d ",a[q[l++]]);
        else
            printf("%d ",a[q[r--]]);
}