【FZUOJ1894 志愿者选拔】

题目描述

西博会马上就要开幕了,电子科技大学组织了一次志愿者选拔活动。
参加志愿者选拔的同学们排队接受面试官们的面试。参加面试的同学们按照先来先面试并且先结束的原则接受面试官们的考查。
面试中每个人的英语口语能力是主要考查对象之一。
作为主面试官的John想知道当前正在接受面试的同学队伍中口语能力值最高的是多少。于是他请你帮忙编写一个程序来计算。

输入格式

输入数据第一行为一整数 T,表示有 T(T<=5)组输入数据。
每组数据第一行为“START”,表示面试开始。
接下来的数据中有三种情况:
1 C NAME KY_VALUE 名字为 NAME 的口语能力值为 KY_VALUE 的同学加入面试队伍。

(名字长度不大于5,0<=KY_VALUE<=1,000,000,000)。

2 G 排在面试队伍最前面的同学面试结束离开考场。
3 Q 主面试官 John 想知道当前正在接受面试的队伍中口语能力最高的值是多少。
最后一行为”END”,表示所有的面试结束,面试的同学们可以依次离开了。
所有参加面试的同学总人数不超过 1,000,000。

输出格式

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

样例数据 1

输入

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

输出

1000000000
0
-1
200
100
500

看题目感觉就是维护单调队列……开一个队列其中人先后顺序和能力值是单调了,其中显然若后来的人能力比队尾的人能力值还高,那他又被后删除,显然是可以替换掉的,就这样一直删啊删直到不满足条件为止,至于出队么,记录一个时间,看队首元素的时间是否<=现在出队的时间就行,若gotime==nowtime就是队列空的时候输出-1即可,话说为啥FZUOJ能AC然而我们学校OJ就TLE了活生生3000ms啊!
下面是在FZUOJ上过了的代码:
stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*