济南学习D1T1

【问题描述】

栈是一种强大的数据结构，它的一种特殊功能是对数组进行排序。例如，借助一个栈，依次将数组1,3,2按顺序入栈或出栈，可对其从大到小排序：

1入栈；3入栈；3出栈；2入栈；2出栈；1出栈。

在上面这个例子中，出栈序列是3,2,1，因此实现了对数组的排序。

遗憾的是，有些时候，仅仅借助一个栈，不能实现对数组的完全排序。例如给定数组2,1,3，借助一个栈，能获得的字典序最大的出栈序列是3,1,2：

2入栈；1入栈；3入栈；3出栈；1出栈；2出栈。

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

【输入格式】

输入共行。

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

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

【输出格式】

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

【样例输入】

2 1 3

【样例输出】

3 1 2

【样例解释】

这回山里有座塔。

【数据规模与约定】

对于的数据(30%)，10³。

对于的数据(60%)，10⁵。

对于的数据(100%)，10⁶。

____________________________________________________________________________

一读题目就知道用贪心，找出序列中最大的，输出，前面的入栈，然后比较栈顶和未入栈最大元素的大小，如果栈顶大则输出栈顶所有大的元素，否则重复上面的步骤，继续把剩余未入栈的最大元素前的栈，输出……直到所有元素输出。

可是发现不可能过所有的点，关键在于找未入栈的最大元素比较耗费时间。区间求最大值，RMQ,可是很难写，忘的差不多了。于是，冥思苦想后，单调队列。

题目中并不是求任意区间的最大值（1），而是求已知最大值的右侧区间的最大值（2），而这个最大值（2）一定不比最大值（1）大，也就是小于等于，因此符合单调性。

—————————————————————————————————————————————————

 1 #include<cstdio>

 2 #include<iostream>

 3 #include<cstring>

 4

 5 using namespace std;

 6 int sz[1000010],n;

 7 int stk[1000010],top=-1;

 8 int que[1000010],tail=-1,head=-1;

 9 void readint(int &x)

10 {

11     char c=getchar();

12     for(;c>'9'||c<'0';c=getchar());

13     x=0;

14     for(;c>='0'&&c<='9';c=getchar())x=x*10+c-'0';

15 }

16 void pushq(int x)

17 {

18     while(tail>-1&&que[tail]<x)tail--;

19     tail++;

20     que[tail]=x;

21 }

22 bool qk()

23 {

24     return tail==head;

25 }

26 int main()

27 {

28     freopen("haha.in","r",stdin);

29     freopen("haha.out","w",stdout);

30     readint(n);

31     for(int i=0;i<n;i++)

32     {

33         readint(sz[i]);

34         pushq(sz[i]);

35     }

36     int q,i=0;

37     while(!qk())

38     {

39         while(sz[i]!=que[head+1])

40         stk[++top]=sz[i],i++;

41         printf("%d ",sz[i]);

42         head++;i++;

43         if(!qk())

44         while(top>=0&&stk[top]>que[head+1])

45         printf("%d ",stk[top--]);

46     }

47     while(top>=0)

48         printf("%d ",stk[top--]);

49     fclose(stdin);

50     fclose(stdout);

51     return 0;

52 }

巴特西

济南学习D1T1_haha

最新文章

热门文章