2018.9.26 2018NOIP冲刺之栈

qxds 2018-09-27 原文

最小字典序（stack）

输入序列中有 n 个正整数，栈 S 开始为空。

你每次只可以进行下面两种操作之一：① 将输入序列头端的数据移至 S 栈顶（进 S 栈）；

② 将 S 栈顶元素输出并删除（退 S 栈）。

当然，输入序列非空时才可进行①操作，S 非空时才可进行②操作。

当①和②的操作都无法执行时，一定得到 n 个数据的一个输出序列。

由于①和②混搭的次序不同，导致相应的输出序列也各不相同，

请你求出能够得到的输出序列中字典序最小的一个序列。所谓字典序最小可以这样理解：首元素尽量小，在首元素最小的序列中第二元素尽可能小、在前 2 数据字典序最小的序列中，第三项尽可能小…，直至 n 项全部排完。

【输入输出说明】

输入文件 stack.in 第一行仅有一个正整数 n，表示输入序列中数据的个数。

第二行就是输入序列中依次排列的 n 个数据，相邻两数据间有一个空格。

输出文件 stack.out 中仅有一行 n 个数，就是字典序最小的输出序列，相邻整数间用一个空格隔开。

【输入输出样例】

stack.in:

2 3 1 4

stack.out:

1 3 2 4

【样例说明】

得到最小字典序的操作序列为：①①①②②②①②

【数据说明】

60%的数据 n<12；

80%的数据 n<1000；

100%的数据 n<100000,其他数据在 int 范围。

首先我们发现题目是区赛的第二个题，按照往年的惯例，第二个题以贪心模拟为主

而因为要求按照字典序输出，很明显应该满足前面的数尽可能小

于是我们得到了贪心思路：

（1）因为输入序列是单向的，所以可以使用一个idx表示当前处理到第几位

（2）每次查找从前往后最小的数，在这个数的位置压栈

（3）首先弹出第一个数，之后判断每一个栈顶的数是否小于后面最小的数

（4）若栈顶等于后面最小的数，因为输入序列是单向的，所以应该尽可能先弹出前面的数

（5）为了节约时间，初始化book数组，用book[i]表示第i个数至第n个数之间最小的数的最小编号（可以利用递推实现）

上代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<stack>
#define _ 0
#define olinr return
#define love_nmr 0
using namespace std;
int n,a[100050],book[100050],idx;
int main()
{
    freopen("stack.in","r",stdin);
    freopen("stack.out","w",stdout);
    int i,j;
    stack<int> s;
    scanf("%d",&n);
    for(i=1;i<=n;i++)scanf("%d",&a[i]);
    book[n]=n;
    for(i=n-1;i>=1;i--)
    {
        if(a[i]<=a[book[i+1]])book[i]=i;
        else book[i]=book[i+1];//初始化，若第i-1位置的数小于从第i至第n位置的数则更新book[i-1]，否则延续 
    }
    bool flag=false;//判断是否首位 
    while(1)
    {
        if(idx==n+1)
        {
            while(!s.empty())
            {
                printf("%d ",s.top());
                s.pop();
            }
            return 0;
        }//处理到输入序列最后一位，全部弹出 
        if(!flag)idx=1,flag=true;
        for(i=idx;i<=book[idx];i++)s.push(a[i]);//压栈 
        idx=i;//更新idx 
        if(!s.empty())
        {
            printf("%d ",s.top());
            s.pop();//弹出栈顶 
        }
        while(!s.empty()&&s.top()<=a[book[idx]])
        {
            printf("%d ",s.top());
            s.pop();//继续弹出 
        }
    }
    olinr ~~love_nmr-(0^_^0);
}