XieNaoban's Blog
0%

算法竞赛入门经典(第2版) 5-7UVa12100 - Printer Queue

发表于 更新于 分类于 ， 阅读次数： 评论次数：
本文字数： 1k 阅读时长 ≈ 1 分钟

题意：一堆文件但只有一个打印机，按优先级与排队顺序进行打印。也就是在一个可以插队的的队列里，问你何时可以打印到。至于这个插队啊，题目说”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）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
//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了而且方便的很，是不是更快区别不大，也不高兴再换个方法试试了。