当前位置 博文首页 > 可惜浅灰的博客：queue应用：UVA12100 打印队列
题目描述：
? ? ? ?学生会里只有一台打印机，但是有很多文件需要打印，因此打印任务不可避免地需要等待。有些打印任务比较急，有些不那么急，所以每个任务都有一个1～9间的优先级，优先级越高表示任务越急。
? ? ? ? 打印机的运作方式如下：首先从打印队列里取出一个任务J，如果队列里有比J更急的任务，则直接把J放到打印队列尾部，否则打印任务J（此时不会把它放回打印队列）。 输入打印队列中各个任务的优先级以及所关注的任务在队列中的位置（队首位置为0），输出该任务完成的时刻。所有任务都需要1分钟打印。例如，打印队列为{1,1,9,1,1,1}，目前处于队首的任务最终完成时刻为5。
? ? ? ? 输入T 接下来T组数据 每组数据输入N，TOP。接下来N个数，TOP代表队列首。
解题思路：
? ? ??1、题目中的队列已经明示了这道题要用queue，在输入了任务的优先级之后，要按照优先级从大到小排序，要使用sort来对它进行排序，建立优先级递减数组。
? ? ? 2、因为输入的序列中的元素有相同值的元素，所以有些麻烦，只能通过下标来区元素，队列中存储输入元素的下标。
? ? ? 3、用一个变量j遍历优先级数组，若发现队头对应的输入元素不是优先级最高，放回队尾；若发现队头对应的输入元素为优先级最高，向后移动j，代表这个元素已经被打印，同时时间+1；若发现元素是TOP，直接返回做种完成时间。
?
代码实现：
#include <iostream>
using namespace std;
#include <queue>
#include <vector>
#include <algorithm>
void Solve(const int& n, const int& top)
{
vector<int> sup; //存放优先级
vector<int> input; //存放输入序列
queue<int> q; //存放下标
int elem = 0;
for (int i = 0; i < n; i++)
{
cin >> elem;
sup.push_back(elem);
input.push_back(elem);
q.push(i);
}
sort(sup.begin(), sup.end(), greater<int>()); //按优先级从大到小排序
int time = 0;
int j = 0; //优先级队列下标
while(j < n)
{
int t = q.front();
if (input[t] == sup[j])
{
if (t == top)
{
time++;
cout << time << endl;
return;
}
else
{
time++;
j++;
q.pop();
}
}
else
{
q.pop();
q.push(t);
}
}
}
int main()
{
int T = 0, N = 0, TOP = 0;
cin >> T;
while (T--)
{
cin >> N >> TOP;
Solve(N, TOP);
}
return 0;
}