首页 > 代码库 > UVA 12100 打印队列(STL deque)
UVA 12100 打印队列(STL deque)
题意：
给定n个优先级打印队列，然后从0开始编号到n-1。出队一个元素，如果他是队列中优先级最高的，打印（耗时一分钟），否则放到队尾（不耗时）。给定一个m，求位置m的文件打印的时间。
分析：
用一个priority_queue去寻找优先级最高的元素，然后用一个deque<pair<int,int> >去模拟队列 pair第一个元素是优先级， 第二个是序号。 如果第一元素跟优先级相同，就出队，否则出队后插入队尾。
（其实这题用queue也可以，不过deque好处是可以在队头插入，而且速度不慢）
1 #include <bits/stdc++.h>
2 using namespace std;
3 typedef pair<int, int > PII;
4 int n, m;
5 int main()
6 {
7 ios::sync_with_stdio(false);
8 #ifdef LOCAL
9 freopen("1.txt","r",stdin);
10 #endif // LOCAL
11 int t;
12 cin >> t;
13 while(t--)
14 {
15 cin>>n>>m;
16 priority_queue<int,vector<int>, less<int> > pq;
17 deque<PII> dq;//pair第一个是优先级 第二个是序号
18 int pos = 0;
19 for(int i = 0 ; i < n; i++)
20 {
21 int p;
22 cin>>p;
23 pq.push(p);
24 dq.push_back(make_pair(p,pos));
25 pos++;
26 }
27 int res = 0;
28 int print = 0;
29 while(1)
30 {
31 int top = pq.top();
32 pq.pop();
33 while(dq.front().first!= top)
34 {
35 PII f = dq.front();
36 dq.pop_front();
37 dq.push_back(f);
38 }
39 if(dq.front().second == m)
40 {
41 ++res;
42 break;
43 }
44 else
45 {
46 dq.pop_front();
47 ++res;
48 }
49 }
50 cout << res << "\n";
51 }
52
53 }
UVA 12100 打印队列(STL deque)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。