[刷题]算法竞赛入门经典(第2版) 5-7/UVa12100 - Printer Queue

时间:2024-04-10 09:36:10

题意:一堆文件但只有一个打印机,按优先级与排队顺序进行打印。也就是在一个可以插队的的队列里,问你何时可以打印到。至于这个插队啊,题目说”Of course, those annoying term papers that others are printing may have to wait for quite some time to get printed, but that’s life.“嗯,这就是生活。


代码:(Accepted, 0ms)

//UVa12100 - Printer Queue
#include<iostream>
#include<queue>
using namespace std;
int T,M,N;
int main()
{
//freopen("in.txt", "r", stdin);
scanf("%d", &T);
while (T--) {
scanf("%d%d", &N, &M);
queue<int> q;
priority_queue<int> p;
int time = 1;
for (int i = 0;i < N;++i){
int tmp;
scanf("%d", &tmp);
q.push(tmp), p.push(tmp);
}
while (true) {
if (q.front() == p.top()) {
if (!M) break;
q.pop(), p.pop();
++time;
}
else {
q.push(q.front());
q.pop();
}
if (--M == -1) M = N - time;
}
printf("%d\n", time);
}
return 0;
}

分析:采用了队列和优先队列。排的队存在队列q里,每读取一个,与p的top()比对,若一致,则弹出p和q的首个元素已打印的份数time进行++,否则p的首元素放最后面去。这个优先队列就是比大小来的,只不过用着方便。

一遍过,哈哈,开心,前两天的题目总是WA和RE,现在终于挽回一点心情。本来还想了好几个办法的,或许比这个还要快一点,但是这章就是让你练习STL嘛,而且这个方法已经0ms了而且方便的很,是不是更快区别不大,也不高兴再换个方法试试了。