首页 > 代码库 > haha

haha

2024-08-19 04:35:58   217人阅读

 技术分享

 

【问题描述】

　　栈是一种强大的数据结构，它的一种特殊功能是对数组进行排序。例如，借助一个栈，依次将数组1,3,2按顺序入栈或出栈，可对其从大到小排序：1入栈；3入栈；3出栈；2入栈；2出；1出栈。在上面这个例子中，出栈序列是3,2,1，因此实现了对数组的排序。遗憾的是，有些时候，仅仅借助一个栈，不能实现对数组的完全排序。例如给定数组2,1,3，借助一个栈，能获得的字典序最大的出栈序列是3,1,2：2入栈；1入栈；3入栈；3出栈；1出栈；2出栈。

　　请你借助一个栈，对一个给定的数组按照出栈顺序进行从大到小排序。当无法完全排序时，请输出字典序最大的出栈序列。

【输入格式】

　　输入共2行。

　　第一行包含一个整数n，表示入栈序列长度。

　　第二行包含n个整数，表示入栈序列。输入数据保证给定的序列是1到n的全排列，即不会出现重复数字。

【输出格式】

　　仅一行，共n个整数，表示你计算出的出栈序列。

【样例输入】

　　3

　　2 1 3

【样例输出】

　　3 1 2

【样例解释】

　　这回山里有座塔。

【数据规模与约定】

　　对于30%的数据，1<=N<=10^3。

　　对于60%的数据，1<=N<=10^5。

　　对于100%的数据，1<=N<=10^6。

【题目分析】

　　f数组处理出到目前可以输出的最大值，要倒叙处理

　　

#include<iostream>#include<cstdio>#include<cstring>#define ge getchar()using namespace std;int a[1000001],f[1000001],s[1000001];int n,k=1;int read(){    int x=0;char ch=ge;    while(ch<‘0‘||ch>‘9‘) ch=ge;    while(ch>=‘0‘&&ch<=‘9‘)    {        x=x*10+ch-‘0‘;ch=ge;    }    return x;}int main(){    freopen("haha.in","r",stdin);    freopen("haha.out","w",stdout);    n=read();    for(int i=0;i<n;i++)        a[i]=read();    for(int i=n-1;i>=0;i--)        f[i]=max(a[i],f[i+1]);    s[0]=-1;    for(int i=0;i<n;i++)    {        s[k++]=a[i];        while(k!=0&&s[k-1]>f[i+1])            printf("%d ",s[--k]);    }    fclose(stdin);    fclose(stdout);    return 0;}

 

haha


联系
我们