Problem 1894 志愿者選拔

Accept: 2308 Submit: 7003
Time Limit: 1500 mSec Memory Limit : 32768 KB

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

Source

福州大學第七屆程序設計競賽

單調隊列問題，雖然不難，現在我還有點懵。

#include <iostream> #include <cstdio> #include<cstring> using namespace std; int x; char a[10]; int ms[1000001],q[1000001]; int main(){int t;cin>>t;while(t--){int front=0,tail=-1;int front2=0,tail2=-1;scanf("%s",a);if(a[0]=='S') while(1){scanf("%s",a);if(a[0]=='E') break;switch(a[0]){case 'C':scanf("%s",a);scanf("%d",&x);tail2++;ms[tail2]=x;while(tail>=front&&x>q[tail]) tail--;tail++;q[tail]=x;break;case 'G':if(front2<=tail2){if(ms[front2]==q[front])front++;front2++;}break;case 'Q':if(front2<=tail2) printf("%d\n",q[front]);else printf("-1\n");}}}return 0; }

總結

以上是生活随笔為你收集整理的FZU 1894 志愿者选拔的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。