【UVA No. 12100】 打印队列 Printer Queue_pv 打印队列

【UVA No. 12100】 打印队列 Printer Queue

洛谷题目地址

【题意】

在计算机学生会里只有一台打印机，但是有很多文件需要打印，因此打印任务不可避免地需要等待。有些打印任务比较急，有些不那么急，所以每个任务都有一个1～9的优先级，优先级越高表示任务越急。

打印机的运作方式：首先从打印队列里取出一个任务J，如果队列里有比J更急的任务，则直接把J放到打印队列尾部，否则打印任务J（此时不会把它放回打印队列）。

输入打印队列中各个任务的优先级 以及 你的任务在队列中的位置（队首位置为0），输出该任务完成的时刻。所有任务都需要1分钟打印。例如，打印队列为{1,1,9,1,1,1}，目前处于队首的任务最终完成时刻为5。

【输入输出】

输入：

第1行为测试用例数T （最多100个）；每个测试用例的第1行都包括n （1≤n ≤100）和m （0≤m ≤n −1），其中n 为打印任务
数量，m 为你的任务序号（从0开始编号）。接下来为n 个数，为n 个打印任务的优先级。

输出：

对于每个测试用例，都单行输出你的作业打印完成的分钟数。

【样例】

【思路分析】

用一个队列存储打印任务，还需要知道当前队列中优先级最高是多少。

首先从队首取出一个任务J，如果J的优先级不低于队列中的最高优先级，则直接打印，否则将任务J放入队尾。
怎么知道当前队列中的最高优先级呢？最简单的办法就是按优先级非递增（允许相等的递减）排序，排序的时间复杂度为O (n logn )。如果写一个函数来查找当前队列中的最高优先级，则每次查找的时间复杂度为O (n)，在最坏情况下执行n 次，时间复杂度为O (n^2 )。

【算法设计】

1. 读入T ，表示T 组数据。
2. 读入n 、m ，表示打印任务的个数和你要打印的任务编号。
3. 读入优先级序列，将其存储在a []、b []两个数组中，并将优先级序列的下标依次（从0开始）放入队列q 。
4. b []数组非递增排序，w =0，k =0，w 用来取最高优先级的下标，k 用来计数已打印了多少个任务。
5. 如果队列q 非空，则取出队头下标t ，它的优先级为a [t]，max=b [w ]。如果a [t ]<max，则t 出队后被放入队尾，否则将t与m 进行比较，如果相等，则输出++k ，跳出循环；如果不相等，则出队，k ++，w ++。
6. 在T 组数据处理完毕后结束。

【完美图解】

① 以下面的输入样例为例，n =4，m =2，即共有4个打印任务，你的打印任务编号为2。

4 2
1 2 3 4
1
2

② 读入优先级序列，将其存储在a []、b []两个数组中，并将优先级序列的下标依次（从0开始）放入队列q

③ b []数组非递增排序，初始化w =0，k =0

④ 取队头t =0，其优先级为a [0]=1，max=b [0]=4，a [0]<max，则将t 出队并放入队尾

⑤ 取队头t =1，其优先级为a [1]=2，max=b [0]=4，a [1]<max，则将t 出队并放入队尾。

⑥ 取队头t =2，其优先级为a [2]=3，max=b [0]=4，a [2]<max，则将t 出队并放入队尾。

⑦ 取队头t =3，其优先级为a [3]=4，max=b [0]=4，a[3]=max，可以打印该任务。t ≠m ，不是你的打印任务，出队，k++，w ++，此时w =1，k =1

⑧ 取队头t =0，其优先级为a [0]=1，max=b [1]=3，a [0]<max，则将t 出队并放入队尾。

⑨ 取队头t =1，其优先级为a [1]=2，max=b [1]=3，a [1]<max，则将t 出队并放入队尾。

⑩ 取出队头t =2，其优先级为a [2]=3，max=b [1]=3，a[2]=max，可以打印该任务。t =m ，是你的打印任务，输出++k ，此时k =2，输出2，表示打印你的任务分钟数2。

【算法实现】

#include<iostream>
#include<string>
#include<queue>
#include<vector>
#include<algorithm>

using namespace std;

int main(){
	
	int T , n , m;
	
	cin >> T;
	
	for(int i = 0; i < T ; i ++){
		
		queue<int> q;
		vector<int> a , b;
		
		int k = 0;
		int x;
		
		cin >> n >> m;
		
		for(int j = 0 ; j < n ; j ++){
			
			cin >> x;
			a.push_back(x);
			b.push_back(x);
			q.push(j);	
		}
		
		sort(b.begin() , b.end() , greater<int>());  //自定义排序，降序
		
		int w = 0;
		int max = 0;
		
		while(!q.empty()){
			
			max = b[w];
			int t = q.front();
			if(a[t] < max){
				q.pop();
				q.push(t);
			}
			else{
				
				if(t == m){
					cout << ++k << endl;
					break;
				}
				else{
					
					q.pop();
					k ++;
					w ++;
					
				}	
			}
		} 
	}
	return 0;
}
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

这里UVA那边挂掉了，跑一下测试样例

OK。