本题使用对顶堆做法。
为了动态维护中位数,我们可以建立两个堆 :一个大根对,一个小根堆。
用法:在动态维护的过程中,设当前的长度为length,大根堆存从小到大排名 $1 \thicksim \dfrac{m}{2} $ 的整数,小根堆存小到大排名 $ \dfrac{m}{2} + 1 \thicksim m $ 的整数
如何动态维护?顾名思义,动态,即边输入边处理。显然,为了维护中位数,我们还要不断地维护两个堆的\(size\)
每次新读入一个值,就 \(\begin{cases}插入大根堆&x < 中位数\\插入小根堆&x\geqslant中位数\end{cases}\) ,然后维护。
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstdio>
using namespace std;
priority_queue<int,vector<int>,greater<int> >xg;//С¸ù¶Ñ
priority_queue<int,vector<int>,less<int> >dg;//´ó¸ù¶Ñ
int T;
void maintenance(){
int l1 = dg . size();
int l2 = xg . size();
while(l1 > l2){
int tmp = dg . top();
dg . pop();
xg . push(tmp);
l1 --;
l2 ++;
// l1 = dg . size();
// l2 = xg . size();
}
while(l2 - l1 > 1){
int tmp = xg . top();
xg . pop();
dg . push(tmp);
// l1 = dg . size();
// l2 = xg . size();
l1 ++;
l2 --;
}
}
void work(){
while(!dg.empty())dg.pop();
while(!xg.empty())xg.pop();
int id, n, data,cnt = 0;
cin >> id >> n;
cout << id << " " << (n + 1) / 2 << endl;
for(int i = 1;i <= n;i ++){
cin >> data;
if(i == 1){
xg . push(data);
} else if(data < xg . top()){
dg . push(data);
// cout << "indg";
maintenance();
} else {
xg . push(data);
maintenance();
}
if(i & 1){
cout << xg . top() ;
cnt ++ ;
if(i == n || cnt % 10 == 0)
cout << endl;
else cout << " ";
}
}
}
int main(){
// freopen("RMPOJ.in","r",stdin);
// freopen("RMPOJ.out","w",stdout);
ios :: sync_with_stdio(false);
cin >> T;
while(T --){
work();
}
return 0;
}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章