首页 > 代码库 > 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)