fzu 1894 志愿者选拔

题目链接：http://acm.fzu.edu.cn/problem.php?pid=1894
解题思路：单调队列
 1 ///////////////////////////////////////////////////////////////////////////
 2 //problem_id: fzu 1894
 3 //user_id: SCNU20102200088
 4 ///////////////////////////////////////////////////////////////////////////
 5 
 6 #include <algorithm>
 7 #include <iostream>
 8 #include <iterator>
 9 #include <iomanip>
10 #include <cstring>
11 #include <cstdlib>
12 #include <string>
13 #include <vector>
14 #include <cstdio>
15 #include <cctype>
16 #include <cmath>
17 #include <queue>
18 #include <stack>
19 #include <list>
20 #include <set>
21 #include <map>
22 using namespace std;
23 
24 ///////////////////////////////////////////////////////////////////////////
25 typedef long long LL;
26 const double PI=acos(-1.0);
27 ///////////////////////////////////////////////////////////////////////////
28 
29 ///////////////////////////////////////////////////////////////////////////
30 //Add Code:
31 struct Node{
32     int key,tag;
33     Node(int k=0,int t=0):key(k),tag(t){}
34 }q[1000005];
35 ///////////////////////////////////////////////////////////////////////////
36 
37 int main(){
38     ///////////////////////////////////////////////////////////////////////
39     //Add code:
40     int T,val;
41     char s[10],t[10];
42     scanf("%d",&T);
43     while(T--){
44         int head=1,tail=0,i=0,now=1;
45         while(scanf("%s",s)){
46             if(s[0]=='S') continue;
47             if(s[0]=='E') break;
48             if(s[0]=='C'){
49                 scanf("%s%d",t,&val);
50                 while(tail>=head && q[tail].key<=val) tail--;  //舍弃当前队伍中排在前面且rp值<=val的人
51                 q[++tail]=Node(val,++i);
52             }
53             else if(s[0]=='G'){
54                 if(q[head].tag==now) head++;  //若当前rp值最大者面试结束，移到下一位，否则不动
55                 now++;
56             }
57             else if(s[0]=='Q'){
58                 if(head>tail) printf("%d
",-1);  //当前没有人正在接受面试
59                 else printf("%d
",q[head].key);
60             }
61         }
62     }
63     ///////////////////////////////////////////////////////////////////////
64     return 0;
65 }
66 
67 ///////////////////////////////////////////////////////////////////////////
68 /*
69 Testcase:
70 Input:
71 2
72 START
73 C Tiny 1000000000
74 C Lina 0
75 Q
76 G
77 Q
78 END
79 START
80 Q
81 C ccQ 200
82 C cxw 100
83 Q
84 G
85 Q
86 C wzc 500
87 Q
88 END
89 Output:
90 1000000000
91 0
92 -1
93 200
94 100
95 500
96 */
97 ///////////////////////////////////////////////////////////////////////////