#STL008. 紧急任务池
紧急任务池
紧急任务池
任务池最初为空。每个任务有编号 id 和紧急程度 priority。新任务可以随时加入;取任务时,总是先取最紧急的一个。如果几个任务一样紧急,先取编号最小的那个。
支持以下指令:
ADD id priority:加入任务,不输出。TAKE:取出并删除优先级最高的任务,输出它的 id;池为空时输出EMPTY。
一个 id 在整个输入中最多用于一次 ADD,即使对应任务已经被取走,也不能再次使用这个 id。不同任务允许具有相同的 priority。
输入格式
第一行整数 q。接下来 q 行,每行一条上述指令。
输出格式
按 TAKE 出现的顺序,每次输出一行。若没有 TAKE,输出为空。
数据范围
- 1 ≤ q ≤ 200000。
- 每次
ADD满足 1 ≤ id ≤ q,且所有ADD的 id 互不相同。 - 0 ≤ priority ≤ 10⁹。
- 输入保证指令格式合法。
样例 1
输入:
10
TAKE
ADD 5 7
ADD 2 7
ADD 9 3
TAKE
ADD 1 8
TAKE
TAKE
TAKE
TAKE
输出:
EMPTY
2
1
5
9
EMPTY
解释:第一次取任务时任务池为空。编号 5 和 2 的紧急程度都是 7,所以先取 2;随后新加入的编号 1 的紧急程度为 8,先于编号 5 和 9 被取走。最后池为空。
样例 2
输入:
8
ADD 8 0
ADD 3 0
ADD 6 1000000000
TAKE
TAKE
ADD 1 0
TAKE
TAKE
输出:
6
3
1
8
解释:编号 6 的紧急程度最高,先被取走。剩余任务的紧急程度均为 0,依次按当前池中的编号从小到大取出:先 3,加入 1 后先 1,最后 8。