TIOJ 2026 . 正手不精

題目鏈接:https://tioj.ck.tp.edu.tw/problems/2026

動態中位數

維護一個大根堆和一個小根堆
大根堆存小於等於中位數的數
小根堆存大於中位數的數
插入的數如果小於等於中位數就丟進大根堆
比中位數大就丟進小根堆
奇數情況下
大根堆的數字比小根堆多1則大根堆的top為中位數

以下為code

#include<bits/stdc++.h>

#include<bits/extc++.h>

using namespace std;

using namespace __gnu_cxx;

using namespace __gnu_pbds;

using ll = long long;

#define AC ios::sync_with_stdio(0),cin.tie(0);

int main()

{

AC

int q,n,x;

cin>>q;

std::priority_queue<int> mx;

std::priority_queue<int,vector<int>,greater<int>> mn;

cin>>n>>x;

mx.emplace(x);

while(--q)

{

cin>>n;

if(n==1)

{

cin>>x;

if(x>mx.top()) mn.emplace(x);

else mx.emplace(x);

if(mx.size()>mn.size()&&mx.size()-mn.size()>1) mn.emplace(mx.top()),mx.pop();

if(mn.size()>mx.size()) mx.emplace(mn.top()),mn.pop();

}

else cout<<mx.top()<<'\n';

}

}