题目大意
这是一道优先队列的题,题目给定 n 个按顺序的命令,但是可能有的命令不全,让你补全所有的命令,并且要求让总数最少。
思路
用优先队列模拟,
如果输入的是insert那就直接加入队列;
如果输入的是removeMin就要判断一下队列此时是否为空,如果为空就先insert 1.再removeMin;
如果输入的是getMin就要判断输入的数字x是否等于队列首元素q.top(),这个过程用一个循环来完成,如果队列中首元素比它大,那么就加上一个,
如果相等直接取出,如果小于就不断取队列中最小元素。
#include<iostream>
#include<queue>
#include<stdio.h>
using namespace std;
char s[15],t[30];
vector<string> ans;
int main()
{
int n,x;
while(cin>>n)
{
ans.clear();
priority_queue<int, vector<int> , greater<int> > q;
for(int i=0;i<n;i++)
{
scanf("%s",s);
if(s[0]=='i')
{
scanf("%d",&x);
sprintf(t,"insert %d",x);
ans.push_back(string(t));
q.push(x);
}
else if(s[0]=='r')
{
if(q.empty())
{
ans.push_back("insert 1");
q.push(1);
}
ans.push_back("removeMin");
q.pop();
}
else
{
scanf("%d",&x);
while(1)
{
if(q.empty()||q.top()>x)
{
q.push(x);
sprintf(t,"insert %d",x);
ans.push_back(string(t));
}
else if(q.top()==x)
{
break;
}
else
{
ans.push_back("removeMin");
q.pop();
}
}
sprintf(t,"getMin %d",x);
ans.push_back(string(t));
}
}
cout<<ans.size()<<endl;
for(int i=0;i<ans.size();i++)
cout<<ans[i]<<endl;
}
return 0;
}