题目链接
https://codeforces.com/contest/681/problem/C
题意
给出T个操作,每次操作会给出如下内容:
insert x:表示插入数字x到队列中。
removeMin:表示从队列中移除最小值
getMin x:表示从队列中需要获取一个最小值等于x。
思路
我写了好久,要么RT,要么TLE。
就是一个模拟题,不用特判任何数据,但是不好写容易漏判。
用优先队列 + vector即可。
AC代码
#include<iostream>
#include<algorithm>
#include<string>
#include<queue>
#include<cmath>
#include<vector>
#include<map>
#include<stdio.h>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
//#define pb push_back;
vector<string> ss;
vector<int> num;
//vector<pair<int,int>> num;
//num.push_back(make_pair(1/2/3,x));
// int num[1000005]; TLE11
priority_queue<int,vector<int>,greater<int> > Q; //从小到大入入队 push、top
int main()
{
ios::sync_with_stdio(false);
int n;
cin>>n;
string s;
for(int i=0;i<n;i++)
{
int x;
cin>>s;
if(s=="insert")
{
cin>>x;
Q.push(x);
ss.push_back("insert"),num.push_back(x);
}
else if(s=="getMin")
{
cin>>x;
bool flag=0;
while(!Q.empty()) // while(!Q.empty()&&x>Q.top())
{
if(Q.top()>x)
break;
if(Q.top()!=x)
{
Q.pop();
ss.push_back("removeMin");
num.push_back(inf);
}
else
{
flag=1;
ss.push_back("getMin");
num.push_back(x);
break;
}
}
if(!flag)
{
ss.push_back("insert");
num.push_back(x);
Q.push(x);
ss.push_back("getMin");
num.push_back(x);
}
}
else if(s=="removeMin")
{
if(Q.empty())
{
ss.push_back("insert");
num.push_back(0);
Q.push(0);
}
Q.pop();
ss.push_back("removeMin");
num.push_back(inf);
}
}
cout<<ss.size()<<endl;
for(int i=0;i<ss.size();i++)
{
if(num[i]==inf)
cout<<ss[i]<<endl;
else
cout<<ss[i]<<" "<<num[i]<<endl;
}
return 0;
}