NOIP模拟题 kun 栈 贪心 解题报告

思路

贪心一下，找一个最大的数，一个一个找，有这个数就出栈，一直贪心下去就好了。
本来想的是线段树，结果只有60分。。。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
#include<stack>
using namespace std;
const int INF=0x3f3f3f3f;
const int N = 1000005;
bool used[N];
int n,a[N];
stack <int> line;
int main()
{
    freopen("kun.in","r",stdin);
    freopen("kun.out","w",stdout);
    scanf("%d",&n);
    for (int i=1;i<=n;i++) 
    scanf("%d",&a[i]);
    int maxn=n,pos=1;
    while(true)
    {
        while (used[maxn]) maxn--;
        if(!maxn)
        {
            while (!line.empty()) printf("%d ",line.top()),line.pop();
            break;
        }
        if(line.empty()||maxn>line.top())
        {
            while (a[pos]^maxn) 
            line.push(a[pos]),used[a[pos]]=true,pos++;
            used[maxn]=true;pos++;
            printf("%d ",maxn);
        }
        else while(!line.empty()&&line.top()>maxn) 
        printf("%d ",line.top()),line.pop();
    }
    return 0;
}