问题 1367 --第三题 懒羊羊吃草

1367: 第三题 懒羊羊吃草

题目描述

  众所周知,懒羊羊是所有小羊里最贪吃的一只。然而,鲜为人知的是,懒羊 羊也有存储粮食的习惯。而更让大家吃惊的事实是,我们的懒羊羊做事很有条理, 每当他存储一份粮食时,他会专门拿出一个筐来存放。因此,他的仓库里有很多 很多筐的青草。而我们的懒羊羊又是一个经常馋嘴的小羊,每当他想吃草时,就 会从仓库里找出数量最少的一筐草,把它吃掉。可是懒羊羊因为草吃得太多了导 致大脑运转缓慢,所以他不得不向你请求支援,帮他找出他应该吃数量为多少的 青草。

输入

输入文件Lyycc.in,第一行为一个正整数n,表示懒羊羊一共进行了n 次操 作(2<=n<=1000000)。第二行至第n+1 行每行表示一个懒羊羊的操作,当这行形式 为单独一个字符‘q’ 时,表示懒羊羊肚子饿了,要吃掉仓库里当前数量最少的 那份青草;当这行形式为一个字符‘i’和一个整数k 时,表示懒羊羊将一份数 量为k(1<=k<=maxlongint)的青草存入了仓库,‘i’和k 之间用空格隔开。 输入 数据保证每次询问时仓库里都有草可吃且所有操作中懒羊羊至少会吃一次草。

输出

 输出文件Lyycc.out,每当输入为‘q’ 时,输出懒羊羊当前吃掉的那份青草的数量是多少。

样例输入输出

输入#1 复制
5
i 5
i 2
q
i 9
q
输出#1 复制
2
5

提示

样例解释:
共有5 次操作,分别为懒羊羊存入数量 为5 的青草,存入数量为2 的青草,吃掉当 前数量最少的青草(2),存入数量为9 的青 草,吃掉当前数量最少的青草(5)。
数据规模:
30%数据满足1<=n<=3000;
60%数据满足1<=n<=40000;
100%数据满足1<=n<=1000000

序号 标题 作者 发表时间 费用 订购数 操作