AcWing 1543. 栈
原题链接
中等
作者:
RainSure
,
2022-02-24 08:54:21
,
所有人可见
,
阅读 241
利用multiset实现平衡树
#include<iostream>
#include<cstring>
#include<set>
#include<stack>
using namespace std;
stack<int> stk;
multiset<int> up, down;
int n;
void adjust()
{
while(up.size() > down.size()){
down.insert(*up.begin());
up.erase(up.begin());
}
while(down.size() > up.size() + 1){
auto it = down.end();
it --;
up.insert(*it);
down.erase(it);
}
}
int main()
{
cin >> n;
while(n --)
{
string op; cin >> op;
if(op == "Push"){
int x; cin >> x;
stk.push(x);
if(up.empty() || x < *up.begin()) down.insert(x);
else up.insert(x);
adjust();
}else if(op == "Pop"){
if(stk.empty()) cout << "Invalid" << endl;
else{
int x = stk.top();
stk.pop();
cout << x << endl;
auto it = down.end();
it --;
if(x <= *it) down.erase(down.find(x));
else up.erase(up.find(x));
adjust();
}
}else if(op == "PeekMedian"){
if(stk.empty()) cout << "Invalid" << endl;
else{
auto it = down.end();
it --;
cout << *it << endl;
}
}
}
return 0;
}