最小字典序(stack)

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

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

②  将 S 栈顶元素输出并删除(退 S 栈)。

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

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

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

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

【输入输出说明】

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

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

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

【输入输出样例】

stack.in:

4

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);
}

比赛的时候就得了50分

后来发现把a[book[idx]]打成了book[idx] Q_Q

 

版权声明:本文为qxds原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://www.cnblogs.com/qxds/p/9714716.html