UVa 1203

Argus

from Chapter 3. Data Structures :: Fundamental Data Structures :: Examples

Problem

开发一个叫Argus的系统，该系统接收如下指令：

• Register Q_num Period

该指令的对一个“询问”事件进行注册，该“询问”的ID为Q_num，每Period秒系统返回一次询问的结果。当同一个事件有多个结果需要返回的时候，先返回ID较小的“询问”。请输出前K个返回结果的“询问”的ID。

（0 < Q_num ≤ 3000, 0 < Period ≤ 3000, 指令数 ≤ 1000, K ≤ 10000）

Solution

我们利用一个优先队列存放所有指令，并且以下一次返回的时间和Q_num的大小为优先级排序。每次将出队元素输出，并且计算出该指令下一次输出的时间，将它再次放入优先队列中，重复k次即可。

每次队列中都有n个元素，因此时间复杂度为 O(K·logN) 。