AcWing 106. 动态中位数(对顶堆)
原题链接
中等
作者:
五道口预备技术员
,
2021-03-30 21:11:37
,
所有人可见
,
阅读 243
#include <iostream>
#include <queue>
using namespace std;
priority_queue<int> q1, q2;
void Running_median() {
while (q1.size()) q1.pop();
while (q2.size()) q2.pop();
int num, n;
cin >> num >> n;
cout << num << " " << (n + 1) / 2 << endl;
int a;
cin >> a;
cout << a << " ";
q2.push(-a);
int cnt = 1;
for (int i = 2; i <= n; i++){
scanf("%d", &a);
if(a < -q2.top()) q1.push(a);
else q2.push(-a);
int s = q1.size();
if(s > i / 2){
q2.push(-q1.top());
q1.pop();
}
if(s < i/2){
q1.push(-q2.top());
q2.pop();
}
if(i % 2){
cout << -q2.top() << " ";
if(n > 2 * (cnt + 1) && ++cnt % 10 == 0) cout << endl;
}
}
cout << endl;
}
int main(){
int t;
cin >> t;
while(t --) Running_median();
return 0;
}