链接:https://ac.nowcoder.com/acm/contest/58/B
来源:牛客网题目描述
给你一个1->n的排列和一个栈,入栈顺序给定
你要在不打乱入栈顺序的情况下,对数组进行从大到小排序
当无法完全排序时,请输出字典序最大的出栈序列
输入描述:
第一行一个数n 第二行n个数,表示入栈的顺序,用空格隔开,结尾无空格
输出描述:
输出一行n个数表示答案,用空格隔开,结尾无空格
示例1
输入
5 2 1 5 3 4
输出
5 4 3 1 2
说明
2入栈;1入栈;5入栈;5出栈;3入栈;4入栈;4出栈;3出栈;1出栈;2出栈
备注:
对于100%的数据,有1<=n<=1000000,保证给的是一个排列
这种题 算是思维题吧
一般这种题目 要完成题目上的要求 一般是有一定的规律或者说依据题意是有一套方法的
肯定不可能是没有规律 随便出栈进栈的 都是有一个统一的原则的
关键就是找出那个原则
这道题呢 规律就是 我们按照题目给的入栈顺序依次入栈 当遇到这个数组中最大的数的时候 直接将其出栈(他已经是最大了 出栈顺序要求尽量从大到小 所以它一进来就应该直接出去) 然后接着依次入栈 再遇到最大的数(不包括已经出栈的数了)时,同样直接出栈,直到走完一遍,然后把压入栈的数依次出栈就好了。
这个方法呢就是能完成题目要求的方法 至于实现 有很多实现方法
我用的是优先队列+栈
将数先全部放入优先队列里,那么就自动从大到小排好序了,然后遍历入栈顺序 与队头元素(最大的数)比较,若相等,那就直接出栈,同时也出队,若不等,那就入栈,最终,把栈内元素依次弹出来就好了。
代码
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<stack>
#include<queue>
#include<string.h>
#include<math.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+7;
priority_queue<int> q;
stack<int>p;
int a[maxn];
int n;
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
q.push(a[i]);
}
for(int i=0;i<n;i++){
if(a[i]==q.top()){
printf("%d ",q.top());
q.pop();
}
else{
p.push(a[i]);
}
}
while(!p.empty()){
printf("%d ",p.top());
p.pop();
}
return 0;
}