FZU 1894 (双端队列)

Problem 1894 志愿者选拔

Accept: 1166 Submit: 3683
Time Limit: 1500 mSec Memory Limit : 32768 KB

Problem Description

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

Input

< http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KyuTI68r9vt212tK70NDOqtK71fvK/VSjrLHtyr7T0FTX6crkyOvK/b7doaPDv9fpyv2+3bXa0rvQ0M6qobFTVEFSVKGxo6yx7cq+w+bK1L+qyrw8YnI+Cr3Tz8LAtLXEyv2+3dbQ09DI/dbWx+m/9qO6PGJyPgo8dGFibGUgYm9yZGVyPQ=="1" align="center" cellspacing="1" width="80%"> 输入含义 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

2STARTC Tiny 1000000000C Lina 0QGQENDSTARTQC ccQ 200C cxw 100QGQC wzc 500QEND

Sample Output

10000000000-1200100500

Hint

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

Source

福州大学第七届程序设计竞赛题意:一个队列，有入队出队查询操作。查询的时候输出队列中最大值。
思路:单调队列。
代码：

#include 
  
   
#include 
   
     #include 
    
      using namespace std; typedef pair
     
       pi; deque
      
       q; const int N = 15; int num, head, rear, t; char start[N], quit[N]; int main() { scanf("%d", &t); while (t --) { scanf("%s", start); head = 0; rear = 0; while (!q.empty()) q.pop_front(); while (scanf("%s", quit) && strcmp(quit, "END") != 0) { if (quit[0] == 'C') { scanf("%s%d", start, &num); while (!q.empty() && q.back().first < num) { q.pop_back(); } q.push_back(make_pair(num, rear)); rear ++; } else if (quit[0] == 'G') { if (q.front().second == head) q.pop_front(); head ++; } else { if (!q.empty()) printf("%d\n", q.front().first); else printf("-1\n"); } } } return 0; }

Accept: 1166 Submit: 3683 Time Limit: 1500 mSec Memory Limit : 32768 KB