Codeforces #357 C. Heap Operations
传送门：http://codeforces.com/contest/681/problem/C
题目大意
对一个小根堆进行操作，已知每个操作和结果。
现在丢失了一些操作，请合法的复原原来的操作。
题解
贪心即可， getMin 小了，就不停 removeMin ；大了或者堆空了就insert。
removeMin 之前判断一下堆是不是空的，空的就随便insert
代码
|
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 64 65 66 67 68 69 70 71 72 73 74 75 76 77 |
#include<cstdio> #include<set> using namespace std; const int Maxn=1000000+5; multiset<int> heap; int insertHeap(int num){ heap.insert(num); } int getMin(){ return *(heap.begin()); } int popHeap(){ heap.erase(heap.begin()); } int n; char ord[10]; int cnt=0; struct Orders{ short int ord; int x; Orders(){} Orders(short o0,int x0){ ord=o0; x=x0; } }; Orders res[Maxn]; int main(){ //freopen("C.in","r",stdin); scanf("%d",&n); for (int i=1;i<=n;i++){ scanf("%s",ord); if (ord[0]=='r'){ if (heap.empty()){ res[++cnt]=Orders(1,1); }else{ popHeap(); } res[++cnt]=Orders(2,0); }else if (ord[0]=='i'){ int x; scanf("%d",&x); insertHeap(x); res[++cnt]=Orders(1,x); }else{ int x; scanf("%d",&x); while(!heap.empty() && getMin()!=x){ if (getMin()<x){ popHeap(); res[++cnt]=Orders(2,0); }else{ insertHeap(x); res[++cnt]=Orders(1,x); } } if (heap.empty()) { res[++cnt]=Orders(1,x); insertHeap(x); } res[++cnt]=Orders(3,x); } } printf("%d\n",cnt); for (int i=1;i<=cnt;i++){ if (res[i].ord==1){ printf("insert %d\n",res[i].x); } if (res[i].ord==2){ printf("removeMin\n"); } if (res[i].ord==3){ printf("getMin %d\n",res[i].x); } } return 0; } |
原文链接：Codeforces #357 C. Heap Operations
WNJXYKの博客 版权所有，转载请注明出处。
还没有任何评论，你来说两句吧!