Petya has recently learned data structure named "Binary heap".
The heap he is now operating with allows the following operations:
- put the given number into the heap;
- get the value of the minimum element in the heap;
- extract the minimum element from the heap;
Thus, at any moment of time the heap contains several integers (possibly none), some of them might be equal.
In order to better learn this data structure Petya took an empty heap and applied some operations above to it. Also, he carefully wrote down all the operations and their results to his event log, following the format:
- insert x — put the element with value x in the heap;
- getMin x — the value of the minimum element contained in the heap was equal to x;
- removeMin — the minimum element was extracted from the heap (only one instance, if there were many).
All the operations were correct, i.e. there was at least one element in the heap each time getMin or removeMin operations were applied.
While Petya was away for a lunch, his little brother Vova came to the room, took away some of the pages from Petya's log and used them to make paper boats.
Now Vova is worried, if he made Petya's sequence of operations inconsistent. For example, if one apply operations one-by-one in the order they are written in the event log, results of getMin operations might differ from the results recorded by Petya, and some of getMin or removeMin operations may be incorrect, as the heap is empty at the moment they are applied.
Now Vova wants to add some new operation records to the event log in order to make the resulting sequence of operations correct. That is, the result of each getMin operation is equal to the result in the record, and the heap is non-empty when getMin ad removeMin are applied. Vova wants to complete this as fast as possible, as the Petya may get back at any moment. He asks you to add the least possible number of operation records to the current log. Note that arbitrary number of operations may be added at the beginning, between any two other operations, or at the end of the log.
The first line of the input contains the only integer n (1 ≤ n ≤ 100 000) — the number of the records left in Petya's journal.
Each of the following n lines describe the records in the current log in the order they are applied. Format described in the statement is used. All numbers in the input are integers not exceeding 109 by their absolute value.
The first line of the output should contain a single integer m — the minimum possible number of records in the modified sequence of operations.
Next m lines should contain the corrected sequence of records following the format of the input (described in the statement), one per line and in the order they are applied. All the numbers in the output should be integers not exceeding 109 by their absolute value.
Note that the input sequence of operations must be the subsequence of the output sequence.
It's guaranteed that there exists the correct answer consisting of no more than 1 000 000 operations.
2
insert 3
getMin 4
4
insert 3
removeMin
insert 4
getMin 4
4
insert 1
insert 1
removeMin
getMin 2
6
insert 1
insert 1
removeMin
removeMin
insert 2
getMin 2
In the first sample, after number 3 is inserted into the heap, the minimum number is 3. To make the result of the first getMin equal to 4 one should firstly remove number 3 from the heap and then add number 4 into the heap.
In the second sample case number 1 is inserted two times, so should be similarly removed twice.
题目连接：http://codeforces.com/contest/681/problem/C
题意：一个最小值优先的优先队列。inisert x是在优先队列中插入x，removeMin是删除队首元素，getMin x是优先队列返回的最高级元素是x。输出m个操作，使得输入的n个操作能够成立。
思路：优先队列的板子题。
代码：
#include<bits/stdc++.h> using namespace std; char s[100]; struct cmp { bool operator ()(int &a,int &b) { return a>b; } }; priority_queue<int,vector<int>,cmp>Q; int sign[1000100]; int num[1000100]; int main() { int i,j,n,x; cin>>n; getchar(); for(i=0,j=0; i<n; i++) { scanf("%s",s); if(s[0]=='i') { scanf("%d",&x); getchar(); sign[j]=1; num[j++]=x; Q.push(x); } else if(s[0]=='r') { if(!Q.empty()) Q.pop(); else { sign[j]=1; num[j++]=0; } sign[j]=-1; num[j++]=0; } else { scanf("%d",&x); getchar(); while(!Q.empty()&&Q.top()<x) { sign[j]=-1; num[j++]=x; Q.pop(); } if(Q.empty()||Q.top()!=x) { sign[j]=1; num[j++]=x; Q.push(x); } sign[j]=0; num[j++]=x; } } cout<<j<<endl; for(i=0; i<j; i++) { if(sign[i]==0) cout<<"getMin "<<num[i]<<endl; else if(sign[i]==1) cout<<"insert "<<num[i]<<endl; else cout<<"removeMin"<<endl; } return 0; }
传送门：优先队列模板
1 #include<iostream> 2 #include<functional> 3 #include<queue> 4 #include<vector> 5 #include<cstdio> 6 using namespace std; 7 8 //定义比较结构 9 struct cmp1 10 { 11 bool operator ()(int &a,int &b) 12 { 13 return a>b;//最小值优先 14 } 15 }; 16 17 struct cmp2 18 { 19 bool operator ()(int &a,int &b) 20 { 21 return a<b;//最大值优先 22 } 23 }; 24 25 //自定义数据结构 26 struct number1 27 { 28 int x; 29 bool operator < (const number1 &a) const 30 { 31 return x>a.x;//最小值优先 32 } 33 }; 34 struct number2 35 { 36 int x; 37 bool operator < (const number2 &a) const 38 { 39 return x<a.x;//最大值优先 40 } 41 }; 42 int a[]= {14,10,56,7,83,22,36,91,3,47,72,0}; 43 number1 num1[]= {14,10,56,7,83,22,36,91,3,47,72,0}; 44 number2 num2[]= {14,10,56,7,83,22,36,91,3,47,72,0}; 45 46 int main() 47 { 48 priority_queue<int>que;//采用默认优先级构造队列 49 50 priority_queue<int,vector<int>,cmp1>que1;//最小值优先 51 priority_queue<int,vector<int>,cmp2>que2;//最大值优先 52 53 priority_queue<int,vector<int>,greater<int> >que3;//注意“>>”会被认为错误， 54 priority_queue<int,vector<int>,less<int> >que4;////最大值优先 55 56 priority_queue<number1>que5; //最小优先级队列 57 priority_queue<number2>que6; //最大优先级队列 58 59 int i; 60 for(i=0; a[i]; i++) 61 { 62 que.push(a[i]); 63 que1.push(a[i]); 64 que2.push(a[i]); 65 que3.push(a[i]); 66 que4.push(a[i]); 67 } 68 for(i=0; num1[i].x; i++) 69 que5.push(num1[i]); 70 for(i=0; num2[i].x; i++) 71 que6.push(num2[i]); 72 73 74 printf("采用默认优先关系: (priority_queue<int>que;) "); 75 printf("Queue 0: "); 76 while(!que.empty()) 77 { 78 printf("%3d",que.top()); 79 que.pop(); 80 } 81 puts(""); 82 puts(""); 83 84 printf("采用结构体自定义优先级方式一: (priority_queue<int,vector<int>,cmp>que;) "); 85 printf("Queue 1: "); 86 while(!que1.empty()) 87 { 88 printf("%3d",que1.top()); 89 que1.pop(); 90 } 91 puts(""); 92 printf("Queue 2: "); 93 while(!que2.empty()) 94 { 95 printf("%3d",que2.top()); 96 que2.pop(); 97 } 98 puts(""); 99 puts(""); 100 printf("采用头文件"functional"内定义优先级: (priority_queue<int,vector<int>,greater<int>/less<int> >que;) "); 101 printf("Queue 3: "); 102 while(!que3.empty()) 103 { 104 printf("%3d",que3.top()); 105 que3.pop(); 106 } 107 puts(""); 108 printf("Queue 4: "); 109 while(!que4.empty()) 110 { 111 printf("%3d",que4.top()); 112 que4.pop(); 113 } 114 puts(""); 115 puts(""); 116 printf("采用结构体自定义优先级方式二: (priority_queue<number>que) "); 117 printf("Queue 5: "); 118 while(!que5.empty()) 119 { 120 printf("%3d",que5.top()); 121 que5.pop(); 122 } 123 puts(""); 124 printf("Queue 6: "); 125 while(!que6.empty()) 126 { 127 printf("%3d",que6.top()); 128 que6.pop(); 129 } 130 puts(""); 131 return 0; 132 } 133 /* 134 运行结果 ： 135 采用默认优先关系: 136 (priority_queue<int>que;) 137 Queue 0: 138 83 72 56 47 36 22 14 10 7 3 139 140 采用结构体自定义优先级方式一: 141 (priority_queue<int,vector<int>,cmp>que;) 142 Queue 1: 143 7 10 14 22 36 47 56 72 83 91 144 Queue 2: 145 83 72 56 47 36 22 14 10 7 3 146 147 采用头文件"functional"内定义优先级: 148 (priority_queue<int,vector<int>,greater<int>/less<int> >que;) 149 Queue 3: 150 7 10 14 22 36 47 56 72 83 91 151 Queue 4: 152 83 72 56 47 36 22 14 10 7 3 153 154 采用结构体自定义优先级方式二: 155 (priority_queue<number>que) 156 Queue 5: 157 7 10 14 22 36 47 56 72 83 91 158 Queue 6: 159 83 72 56 47 36 22 14 10 7 3 160 */