O(1)查询中位数
C++ STL vector的insert用法整理
思路
思路:使用lower_bound这个函数
使用方法: C++ lower_bound 与 upper_bound 函数
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve()
{
int n, x;
string s;
cin >> n;
vector<int> v, v1;
while (n--)
{
cin >> s;
if (s == "Push")
{
cin >> x;
v1.push_back(x);//v1正常向量
auto it = lower_bound(v.begin(), v.end(), x);//v向量存放中位数
v.insert(it, x);
}
else if (s == "Pop")
{
if (v1.size() == 0) cout << "Invalid\n";
else
{
auto it = lower_bound(v.begin(), v.end(), v1[v1.size() - 1]);
v.erase(it);
cout << v1[v1.size() - 1] << "\n";
v1.pop_back();
}
}
else
{
if (v1.size() == 0) cout << "Invalid\n";
else
{
if (v.size() & 1) cout << v[v.size() / 2] << '\n';
else
cout << v[v.size() / 2 - 1] << "\n";
}
}
}
}
int main()
{
ios_base::sync_with_stdio(false), cin.tie(0);
solve();
return 0;
}