FZU 1894 志愿者选拔单调队列

题目链接：http://acm.fzu.edu.cn/problem.php?pid=1894

Problem Description

世博会马上就要开幕了，福州大学组织了一次志愿者选拔活动。
参加志愿者选拔的同学们排队接受面试官们的面试。参加面试的同学们按照先来先面试并且先结束的原则接受面试官们的考查。
面试中每个人的人品是主要考查对象之一。（提高人品的方法有扶老奶奶过街，不闯红灯等）
作为主面试官的John想知道当前正在接受面试的同学队伍中人品值最高的是多少。于是他请你帮忙编写一个程序来计算。

Input

输入数据第一行为一整数T，表示有T组输入数据。每组数据第一行为”START”，表示面试开始
接下来的数据中有三种情况：

	输入	含义
1	C NAME RP_VALUE	名字为NAME的人品值为RP_VALUE的同学加入面试队伍。(名字长度不大于5，0 <= RP_VALUE <= 1,000,000,000)
2	G	排在面试队伍最前面的同学面试结束离开考场。
3	Q	主面试官John想知道当前正在接受面试的队伍中人品最高的值是多少。

最后一行为”END”，表示所有的面试结束，面试的同学们可以依次离开了。
所有参加面试的同学总人数不超过1,000,000

Output

对于每个询问Q,输出当前正在接受面试的队伍中人品最高的值,如果当前没有人正在接受面试则输出-1。

Sample Input

2 START C Tiny 1000000000 C Lina 0 Q G Q END START Q C ccQ 200 C cxw 100 Q G Q C wzc 500 Q END

Sample Output

1000000000 0 -1 200 100 500

Hint

数据较大建议使用scanf,printf 不推荐使用STL

题目分析：使用优先队列会超时，使用线段树超内存，sort一直排序这个肯定不行啦，我也是醉了，只好用单调队列维护顺序；

推荐博客：单调队列讲解　　　双端单调队列

本题AC代码：

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<queue>
 6 #include<string>
 7 #include<cmath>
 8 #define LL long long
 9 using namespace std;
10 const int N = 1000010 ;
11 LL queu[N];//原始数组
12 LL m_queu[N];//单调递增数组
13 int top,base,m_top,m_base;
14 int build(LL aa)
15 {
16     top++;
17     queu[top] = aa;//进来一个数存入一个数；
18         while(m_top>=m_base)//自顶端向下寻找大于aa的数
19         {
20             if(m_queu[m_top]>aa) break;
21             m_top--;
22 
23         }
24         //如果找到大于aa的数，或者当前队列为空直接存入下一位，空时m_top=-1；
25             m_top++;
26             m_queu[m_top] = aa;
27 }
28 int main()
29 {
30    int T,kk,x,y;
31    LL aa;
32    char s[10],name[10];
33    scanf("%d",&T);
34    while(T--)
35    {
36        scanf("%s",s);
37        if(strcmp(s,"START")==0)
38        {
39            top = -1,base = 0,m_top = -1,m_base =0;//初始化队列
40            memset(queu,-1,sizeof(queu));
41            memset(m_queu,-1,sizeof(m_queu));
42             while(1)
43            {
44                scanf(" %s",s);
45                if(strcmp(s,"END") ==0 ) break;
46                 else if(s[0] == 'C')
47                {
48                    scanf("%s %lld",name,&aa);
49                    build(aa);
50                }
51                else if(s[0] == 'Q')
52                {
53                    if(m_base>m_top) printf("-1
");//队列为空
54                    else printf("%lld
",m_queu[m_base]);//直接输出顶端元素，即为最大值
55                }
56                //此处容易产生疑惑，已经删除的数会不会出现在顶端呢；
57                //答案是会的，当且仅当queue[top] == m_queue[m_top]时会出现在顶端
58                else if(s[0] == 'G')
59                {
60                    //如果顶端数等于要删除的数字，则单调队列底部上移一位；原始队列上移一位
61                    if(queu[base] == m_queu[m_base])
62                     m_base++;
63                    base++;
64                }
65            }
66        }
67    }
68   return 0;
69 }