不确定这个问题需要什么样的算法/数据结构(打印机队列问题)

Question

这在很大程度上是打印机队列问题。

样本输入：

6 0
1 1 9 1 1 1

第一行=两个数字，首先是打印机作业的数量，其次是作业在队列中的位置。

第二行=每个作业的优先级。列出的第一个数字是第一个工作的优先顺序，依此类推。数量越多，优先级就越高。

打印机无限期地运行此循环：

1. 在队列的最前面读作业J。
2. 如果队列中有另一个优先级高于J的作业，请将J移动到队列的末尾。
3. 否则，执行作业J(这需要1分钟完成)并将其从队列中删除。

输出打印机完成工作前的分钟数。

问题是这个位置很重要。因此，正如您在测试用例中所看到的，您的任务是队列中的第一个，这意味着它将被移到后面，因为它不是最高优先级，然后第二个作业也会被移到后面，然后您的作业将在5分钟后完成打印。

我认为LinkedList对此最好，但您必须跟踪最高优先级，这是动态更改的。PriorityQueue的问题是，元素是基于某个比较器插入的，而my结构的初始排序是基于位置的。此外，您也不能添加到一个PriorityQueue的后方。

所以，我被困在这里，因为我知道应该使用哪种结构，或者这个问题是否涉及到任何结构。

Answer 1

编辑:我写到@MinosIllyrien的答案是正确的，但事实并非如此。不过，我想我可以解决我的问题。如果你认为我失败了，可以发表意见。

以下是我自己的解释：

想象一下，你有三类人：

• 比你更重要，
• 和你一样重要
• 不像你那么重要。

在一个公平的世界里，会发生什么？首先是MITY通行证，然后是AIAY，在你排队之前的哪里通过，现在轮到你了(不管有多少种性质:让我们公平一点，但不要太多)。

但是在你们的世界里，每一次一个神的到来，他/她都会改变AIAY的顺序。这不重要，直到最后一天过去。如果他/她在你之前，没问题。但如果他/她在你后面，你和他/她面前的所有AIAY都被移到了后面。所以AIAY的在后面，这个在你面前，而AIAY在你前面的地方，你还在前面。因此，唯一留在你们之后的AIAY是你们和最后一个人之间的人。

编辑:问题是顺序:它们不是按位置排序( MinosIllyrien答案中的问题)，而是按优先级排列，按位置排序。上面这一节没有缺陷，保持不变。

如果需要输出排序的作业，则不需要特定的数据结构。下面是一个简单链表的算法(或者两个数组列表:一个用来存储作业，一个用来标记已执行的作业)

假设作业列表不是空的。

1. 设Ps =有序的优先级集，从最大到最小
2. 设last_pos =0
3. 设P= Ps.pop()和start_pos = last_pos
4. 执行(并移除)优先级为P的所有作业，从start_pos到P的last_pos (从结束到开始进行倒带)
5. 如果Ps不是空的，返回到3，否则结束。

步骤1的时间复杂度为O(n)，对Ps中的每个P，即O(n +n* Ps.size)，则为O( n )。如果您知道优先级的边界，那么步骤1是O(n)，只有桶排序，因此整个序列具有O(n * Ps.size)的复杂性。

Answer 2

这是错误的-我写了为什么在底部：

[把清单看一遍。在索引之前，将每个具有相同优先级或更高优先级的元素计数为一个。索引之后，只将具有严格高优先级的元素计数为元素，直到具有更高优先级的最后一个索引为止。在该索引之后，继续计算与您的索引具有相同优先级的所有元素。这将给出在元素之前打印的元素数量，因此为您自己的元素添加一分钟。

我希望这能帮到你。

编辑：

为了澄清:让我们根据队列中所有元素的优先级重命名它们。L较低，e等于，h较高。W是通缉文件。问题的顺序是：

w e h e e e

我们首先计算w之前的e和h的数目，因为它们将在w之前打印。(e被移到w之前的队列后面，h首先被处理。)在这个例子中，w之前没有元素，所以我们计算0。

在w之后，我们只计算h，因为它们被移动到队列的前面。在这个例子中只有一个。

最后，我们计算w后最后h之后的e数(如果w后面有h)，因为w是在这些e之后移动的，所以我们总共有4个打印作业在我们之前。加上我们自己的印刷作业，我们总共得到五份工作/分钟。

要做到这一点，我们需要查看列表两次，一次查找最后h，一次进行计数。

编辑：

用一个新的例子。假设我们的队列是2，2'，9，8，2，1，7，其中2‘是我们的文档。

发生的第一件事是将前2发送到队列的后面，然后是2'：

2 2' 9 8 2 1 7
2' 9 8 2 1 7 2
9 8 2 1 7 2 2'

然后，9和8被打印，留给我们2，1，7，2，2‘。现在2和1被发送到后面。

2 1 7 2 2'
1 7 2 2' 2
7 2 2' 2 1

7是打印出来的。剩下的是2，2'，2，1。这些是按顺序打印的，2‘作为第5元素整体打印。

如果我们遵循上述程序，我们将将其改写为：

2 2 9 8 2 1 7
e w h h e l h

直到w，我们计算出h的0次和e的1次，这是后面在我们之前打印的2。在w之后，我们计算最后h后的3h和0e‘s，这意味着有三个元素(9、8和7)将在我们自己之前打印，而e和l (2和1)则不会。

总共，我们计算了4种元素印在我们自己的和我们的是第5位。]

我从来没有想过，要素可以进行几轮。当优先级较高的作业按降序排列时，上述情况仍然成立，但正如ruakh所指出的，反例是(1‘，2，1，3)。