题目描述
维护一个集合,初始时集合为空,支持如下几种操作:
I x,插入一个数 x
;
PM,输出当前集合中的最小值;
DM,删除当前集合中的最小值(数据保证此时的最小值唯一);
D k,删除第 k
个插入的数;
C k x,修改第 k
个插入的数,将其变为 x
;
现在要进行 N
次操作,对于所有第 2
个操作,输出当前集合的最小值。
输入格式
第一行包含整数 N
。
接下来 N
行,每行包含一个操作指令,操作指令为 I x,PM,DM,D k 或 C k x 中的一种。
输出格式
对于每个输出指令 PM,输出一个结果,表示当前集合中的最小值。
每个结果占一行。
数据范围
1≤N≤105
−109≤x≤109
数据保证合法。
输入样例:
8
I -10
PM
I -10
D 1
C 2 8
I 6
PM
DM
输出样例:
-10
6
算法1
直接用set模拟堆就可以了
时间复杂度nlogn
C++ 代码
#include<bits/stdc++.h>
using namespace std;
multiset<int> st;
int a[100005];
int cnt=1;
int main()
{
int n;cin>>n;
for (int i=0;i<n;i++)
{
string str;cin>>str;
if(str=="I")
{
int x;cin>>x;
st.insert(x);
a[cnt++]=x;
}
else if (str=="PM")
{
cout<<*st.begin()<<endl;
}
else if (str=="DM")
{
st.erase(st.begin());
}
else if (str=="D")
{
int k;cin>>k;
int t=a[k];
st.erase(find(st.begin(),st.end(),t));
}
else if (str=="C")
{
int k,x;cin>>k>>x;
int t=a[k];
a[k]=x;
st.erase(find(st.begin(),st.end(),t));
st.insert(x);
}
}
}