维护两个栈。一个正常放数据,另一个是排序好的数据。
#include <bits/stdc++.h>
using namespace std;
int main(){
vector<int> data;
vector<int> mdata;
vector<int>::iterator it;
int n;
cin>>n;
while(n--){
string s;
cin>>s;
if(s=="Pop"){
if(data.empty()){
cout << "Invalid"<<'\n';
continue;
}
int dt = data.back();
data.pop_back();
cout << dt << '\n';
it=lower_bound(mdata.begin(),mdata.end(),dt);
mdata.erase(it);
}else if(s=="PeekMedian"){
if(mdata.empty()) {
cout << "Invalid" << '\n';
continue;
}
if(mdata.size()%2==0){
cout << mdata[mdata.size()/2-1] << '\n';
}else{
cout << mdata[(mdata.size()+1)/2-1]<<'\n';
}
}else if(s=="Push"){
int t;
cin>>t;
data.push_back(t);
it = lower_bound(mdata.begin(),mdata.end(),t);
mdata.insert(it,t);
}
}
return 0;
}
附录:
代码 含义
c.front() 返回第一个数据
c.back() 返回数组中的最后一个数据
c.pop_back() 删除最后一个数据
c.push_back(element) 在尾部加一个数据
c.size() 返回实际数据个数(unsigned类型)
c.clear() 清除元素个数 ,N为元素个数
c.resize(n, v) 改变数组大小为 n , n 个空间数值赋为 v ,如果没有默认赋值为 0
c.insert(it, x) 向任意迭代器 it 插入一个元素 x ,
例: c.insert(c.begin() + 2,-1) 将 -1 插入 c[2] 的位置
c.erase(first,last) 删除 [first,last) 的所有元素,
c.begin() 返回首元素的迭代器(通俗来说就是地址)
c.end() 返回最后一个元素后一个位置的迭代器(地址)
c.empty() 判断是否为空,为空返回真,反之返回假
标签:mdata,返回,begin,元素,back,002,L3,堆栈,data
From: https://www.cnblogs.com/chengyiyuki/p/18111397