原题：点击打开链接
有一个堆，给你一些操作，分别是往这个堆加数，移除最小值和查询最小值，让你按照这些操作做，并且要最少次操作，输出这些操作记录。
注意查询最小值x时记得判断当前堆的最小值是否为x，若大于x则插入x，小于则要移除最小值。当堆为空时，必须先插入一个数才能移除最小值。
一道模拟题，用了multiset按照降序来存储堆里面的数值。
#include <cstdio> #include <cstring> #include <string> #include <iostream> #include <algorithm> #include <set> #define inf 1e8 using namespace std; const int maxn=1e5+10; const int maxm=1e6+10; char ss[maxm][15],s[maxn][15]; int a[maxn],c[maxn],a1[maxm],c1[maxm]; multiset<int, greater<int> > b; int main() { char in[]="insert"; char re[]="removeMin"; char ge[]="getMin"; int n; while(scanf("%d",&n)!=EOF) { int cnt=0; for(int i=0;i<n;i++) { scanf("%s",&s[i]); if(s[i][0]=='i') { scanf("%d",&a[i]); } else if(s[i][0]=='g') { scanf("%d",&c[i]); } } for(int i=0;i<n;i++) { if(s[i][0]=='i') { strcpy(ss[cnt],s[i]); a1[cnt]=a[i]; cnt++; b.insert(a[i]); } else if(s[i][0]=='r') { if(!b.empty()) { b.erase(--b.end()); } else { strcpy(ss[cnt],in); a1[cnt]=0; cnt++; b.insert(0); b.erase(--b.end()); } strcpy(ss[cnt],s[i]); cnt++; } else { if(!b.empty()) { if(*(--b.end())==c[i]) { strcpy(ss[cnt],s[i]); c1[cnt]=c[i]; cnt++; } else if(*(--b.end())>c[i]) { strcpy(ss[cnt],in); a1[cnt]=c[i]; cnt++; b.insert(a[i]); strcpy(ss[cnt],ge); c1[cnt]=c[i]; cnt++; } else if(*(--b.end())<c[i]) { while(!b.empty()&&*(--b.end())<c[i]) { strcpy(ss[cnt],re); cnt++; b.erase(--b.end()); } if(b.empty()||*(--b.end())>c[i]) { strcpy(ss[cnt],in); a1[cnt]=c[i]; cnt++; b.insert(c[i]); } strcpy(ss[cnt],ge); c1[cnt]=c[i]; cnt++; } } else { strcpy(ss[cnt],in); a1[cnt]=c[i]; cnt++; b.insert(c[i]); strcpy(ss[cnt],ge); c1[cnt]=c[i]; cnt++; } } } printf("%d\n",cnt); for(int i=0;i<cnt;i++) { if(ss[i][0]=='i') printf("%s %d\n",ss[i],a1[i]); else if(ss[i][0]=='r') printf("%s\n",ss[i]); else printf("%s %d\n",ss[i],c1[i]); } b.clear(); } return 0; }
