Codeforces Round #357 (Div. 2) C. Heap Operations 优先队列

C. Heap Operations

链接：

http://codeforces.com/contest/681/problem/C

题意：

共有3种指令，1:insert x,插入一个值x，2:getMin x，在集合中得到最小值x,3:removeMin，从集合中移除最小值，现在给你n项指令，但其中有缺项，现在让你补全这些缺项

思路：

用一个优先队列来保存集合内元素，然后模拟最后951ms飘过。。

代码：

 1 #include <iostream>
 2 #include <vector>
 3 #include <string>
 4 #include <queue>
 5 #include<functional>
 6 using namespace std;
 7 
 8 vector<pair<int, int>> ans;
 9 priority_queue<int, vector<int>, greater<int> > num;
10 
11 int main() {
12     int n, x;
13     string s;
14     cin >> n;
15     for (int i = 1; i <= n; i++)
16     {
17         cin >> s;
18         if (s[0] != 'r') 
19             cin >> x;
20         if (s[0] == 'i') {
21             num.push(x);
22             ans.push_back(make_pair(1, x));
23         }
24         else if (s[0] == 'g') {
25             while (!num.empty() && num.top() < x) {
26                 num.pop();
27                 ans.push_back(make_pair(3, 0));
28             }
29             if (num.empty() || num.top() != x) {
30                 num.push(x);
31                 ans.push_back(make_pair(1, x));
32             }
33             ans.push_back(make_pair(2, x));
34         }
35         else
36         {
37             if (num.empty()) {
38                 ans.push_back(make_pair(1, 1));
39                 num.push(1);
40             }
41             num.pop();
42             ans.push_back(make_pair(3, 0));
43         }        
44     }
45     cout << ans.size() << endl;
46     for (int i = 0; i < ans.size(); i++)
47     {
48         if (ans[i].first == 1)
49             cout << "insert " << ans[i].second << endl;
50         else if (ans[i].first == 2)
51             cout << "getMin " << ans[i].second << endl;
52         else
53             cout << "removeMin" << endl;
54     }
55     return 0;
56 }