团体程序设计天梯赛
L3-002 特殊堆栈
法一：使用vector维护。维护两个vector：堆栈s和有序数组ordered。push和pop操作分别查找ordered的下界位置，使用insert()或erase()函数操作，时间复杂度为O(n)；peekmedian操作只需要取ordered数组的中间位置值即可，时间复杂度为O(1)。
#include <bits/stdc++.h>
using namespace std;
vector<int> s, ordered;
int main(){
int n;
cin >> n;
for(int i = 0; i <= n - 1; i++){
string temp;
int val;
cin >> temp;
if(temp == "Push"){
cin >> val;
s.push_back(val);
auto it = lower_bound(ordered.begin(), ordered.end(), val);
ordered.insert(it, val);
}
else if(temp == "Pop"){
if(s.empty() == true){
cout << "Invalid" << endl;
continue;
}
else{
val = s[(int)s.size() - 1];
cout << val << endl;
s.pop_back();
auto it = lower_bound(ordered.begin(), ordered.end(), val);
ordered.erase(it);
}
}
else if(temp == "PeekMedian"){
if(s.empty() == true){
cout << "Invalid" << endl;
continue;
}
else{
int des = ((int)s.size() - 1) / 2;
cout << ordered[des] << endl;
}
}
}
return 0;
}