「fzoj1724」排序 - 栈

题目大意

    众所周知，熟练掌握至少一种排序算法是参加NOIP的必备技能。常见的排序算法有冒泡排序、归并排序、快速排序、奇偶排序、猴子排序、梳排序、鸡尾酒排序、臭皮匠排序等。
    在这里，介绍一种利用栈进行排序的方法。例如，当数组中的元素为$1,3,2$时，我们可以利用栈对其进行排序：$1$入栈；$3$入栈；$3$出栈；$2$入栈；$2$出栈；$1$出栈。在这个例子中，出栈序列是$3,2,1$，因而实现了对数组的排序。
    遗憾的是，在不打乱入栈顺序的前提下，有时仅仅借助一个栈是不能实现对数组的完全排序。例如给定数组$2,1,3$，借助一个栈，能获得的字典序最大的出栈序列是$3,1,2$。（$2$入栈；$1$入栈；$3$入栈；$3$出栈；$1$出栈；$2$出栈）
    现请你借助一个栈，在不打乱入栈顺序的情况下，对数组进行从大到小排序。当无法完全排序时，请输出字典序最大的出栈序列。

---

题目分析

考虑用栈维护这样一个贪心策略：维护一个栈，若当前数后面的最大值比栈顶大，根据最大原则，将当前数入栈；否则弹栈直到满足条件。

---

代码

特别卡常数，printf略慢。

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
#include<stack>
using namespace std;

inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

void Put_Int(int x){
	if(!x)return;
	Put_Int(x/10);
	putchar('0'+(x%10));
}

const int maxn=1000005;
int n,a[maxn],Max[maxn];

int max(int x,int y) {
	if(x>y)return x;
	return y;
}

int S[maxn],top=0;

int main() {
	n=Get_Int();
	for(int i=1; i<=n; i++)a[i]=Get_Int();
	for(int i=n; i>=1; i--)Max[i]=max(Max[i+1],a[i]);
	for(int i=1; i<=n; i++) {
		while(top&&S[top]>Max[i]) {
			Put_Int(S[top]);
			putchar(' ');
			top--;
		}
		S[++top]=a[i];
	}
	while(top)Put_Int(S[top--]),putchar(' ');
	return 0;
}