题解：P11289 【MX-S6-T1】「KDOI-11」打印

· · 题解

这是一道非常非常简单的绿题（是谁交了8次，重构了1次代码才过呢~）。

先说一下错的两个地方，以示警告。重构后，第一次错是因为没看清 n,m 的差异，第二次错呢，则是因为忘记了加入 m 台打印机，写成了加入 n 台。

那现在开始讲这题的做法。

首先，为了线性考虑每个文件，我们应该把文件按照下达打印任务的时间排序，记得保存编号。

同时，我们用vector保存每台打印机需要打印的文件的编号，记得最后排序再输出。

然后，我们发现，对于每一个文件来讲，它需要选择的打印机是等待时间最短，且编号最小的打印机。那么我们可以维护一个优先队列，这个优先队列按照每台打印机结束上一次任务的排序，如果结束时间相同，那就按照编号排序。然后每次选取这个优先队列的头就好了……吗？

我们发现，如果一台打印机结束上一个任务的时间比这个文件下达打印任务的时间还早（或相等），那么我们可以认为，这台打印机是无需等待的。对于多台无需等待的打印机，即使他们结束上一次的时间不同，我们也应该只考虑他们的编号大小，而无需考虑结束时间。

那么，再开一个优先队列，维护「可直接用的打印机」即可，按照编号排序。