洛谷题目页面传送门 & UVA12100 Printer Queue 题目页面传送门 题意简述 给你一个打印队列，每个任务都有一个优先级。现在有一个打印机，最多每分钟只能打印一个任务，如果你现在选择打印某个任务，它将在当前队列中排到底部。如果某个任务的优先级比当前队列中剩余的任务高，那么它就排在当前队列中的所有任务的后面。 已知队列顺序，和每个任务的优先级，问打印完一个指定位置的任务，所需要的分钟数。 题目思路 这道题目本质上是一道队列的模拟题目，如果想要在 $O(N^2)$ 的时间内 AC 掉的话，我们需要仔细揣摩题目的性质，思路如下： - 我们考虑不同的任务，它们在完成之后能够对结果所造成的贡献。那么显然正常打印完每一个任务，应该能够直接加上这个任务的优先级吧。 - 但是当某些任务的优先级比较高的时候，我们可以想到，我们应该把这个任务插入到前面的位置，让它短时间内完成，因为它的优先级比前面的任务都要高。 考虑最终的打印状态，假设 $f(i)$ 表示打印位置为 $i$ 的任务所需要的最少时间，那么一共有三种情况： - 这个任务的优先级大于队尾所有任务的优先级，那么我们直接在队尾加上这个任务就行了 - 这个任务的优先级小于队尾任务的优先级，那么我们直接在队尾保持不变，把这个任务插入到队列前面 - 这个任务打印完会使前面的任务都输出，那么我们将其放到一批任务中，所有这一批任务一起运行 显然我们想到可以使用双向链表模拟这个队列，来方便地实现剪切和插入的操作，这样题目就非常简单了，我们按照题意写个模拟即可。