CodeForce 681C 模拟题

题意

有一个数据结构，能执行三种命令：getMin x，removeMin，insert x。现有一些随机的命令，补全这些命令使所有的命令合法，并且最终的命令数最少。

题目分析

这个数据结构可以用优先队列实现insert x永远是合法的命令。removeMin在数据结构为空时不合法，不合法时，我们可以先插入一个任意数使它合法。getMin会在数据空，第一个数比它大，第一个数比它小时不合法。分情况解决

注意

这道题我runtimeError了很久。要特别注意RE，有两种常发生的re的情况。一种情况是数组越界，要么数组开小了，要么程序写错了。另一种情况是容器类，在pop，top这种操作前一定要检查容器是否空。

输出

这道题输出有点麻烦，得先把输出结果都存储下来，最后再一并输出才行。这里有两种方法。两种方法都得用到sprintf()一是用vector<string>保存结果，直接用size()，一并输出。另一种是用一个超长字符串，手动记录命令个数，手动维护超长字符串的指针。 #include<cstdio> #include<queue> #include<vector> #include<string> #include<iostream> #include<cstring> using namespace std; char op[30]; char tmp[30]; int oprand; vector<string> log; priority_queue<int,vector<int>,greater<int> > q; void logRemoveMin() { log.push_back("removeMin"); } void queInsert(int i) { q.push(i); sprintf(tmp,"insert %d",i); log.push_back(tmp); } void logGetMin() { sprintf(tmp,"getMin %d",oprand); log.push_back(tmp); } int main() { int t; while(~scanf("%d",&t)) { log.clear(); while(!q.empty()) q.pop(); while(t--) { scanf("%s",op); if(op[0] == 'r')//removeMin { if(q.empty()) queInsert(1); q.pop(); logRemoveMin(); } else if(op[0] == 'g')//getMin { scanf("%d",&oprand); while(!q.empty() && (q.top() < oprand)) { q.pop(); logRemoveMin(); } if(q.empty() || (q.top() > oprand)) queInsert(oprand); logGetMin(); } else if(op[0] == 'i')//insert { scanf("%d",&oprand); queInsert(oprand); } } int size = log.size(); printf("%lu\n",size); for(int i=0;i<size;i++) cout<<log[i]<<endl; } } #include<cstdio> #include<queue> #include<cstring> using namespace std; char op[30]; int oprand; int cnt; char s[10000000]; int p; priority_queue<int,vector<int>,greater<int> > q; void inputOpration() { scanf("%s",op); if(strcmp(op,"removeMin")) scanf("%d",&oprand); } void printInsert(int i){ char tmp[100]; sprintf(tmp,"insert %d\n",i); int tmpLen = strlen(tmp); sprintf(s+p,"%s",tmp); p += tmpLen; } void printRemoveMin() { cnt++; sprintf(s+p,"removeMin\n"); p += 10; } void queInsert(int i) { cnt++; q.push(i); printInsert(i); } int quePop() { q.pop(); int result = q.top(); printRemoveMin(); return result; } void printGetMin() { cnt++; char tmp[100]; sprintf(tmp,"getMin %d\n",oprand); int tmpLen = strlen(tmp); sprintf(s+p,"%s",tmp); p += tmpLen; } int main() { int t; while(~scanf("%d",&t)) { cnt = p = 0; while(!q.empty()) q.pop(); while(t--) { inputOpration(); if(!strcmp(op,"removeMin")) { if(q.empty()) queInsert(1); q.pop(); printRemoveMin(); } else if(!strcmp(op,"getMin")) { while(!q.empty() && q.top() < oprand) quePop(); if(q.empty() || q.top() > oprand) queInsert(oprand); printGetMin(); } else if(!strcmp(op,"insert")) queInsert(oprand); } printf("%d\n%s",cnt,s); } }