AcWing 106. 动态中位数
原题链接
中等
作者:
骄骄是骄傲的骄骄
,
2022-02-25 16:34:06
,
所有人可见
,
阅读 147
/*
左边是 大根堆
右边是 小根堆
同时 大根堆top < 小根堆top
我们每次取答案,是从小根堆的top获取
并且只有奇数个数时候取,因此 大根堆size==小根堆size-1
当我们插入一个数时,空的情况下直接干到小根堆里面
如果 num>小.top() 小.push(num)
这时候考虑 if 小.size-大.size >= 2
那么把小.top 弹到 大
如果 num<=小.top 大.push(num)
这时候考虑 if 大.size==小.size
那么把大.top 弹到 小
当 i&1 输出 小.top
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
int main(){
int T=0;
cin>>T;
// T个数据集
while(T--){
int id, M;
cin>>id>>M;
cout<<id<<" "<<(M+1)/2<<endl;
// 输出 编号 中位数个数
priority_queue<int, vector<int>, less<int>> down; // 大根堆
priority_queue<int, vector<int>, greater<int>> up; // 小根堆
// 输入每个数
for(int i=0, t; i<M; i++){
scanf("%d", &t);
if(up.empty() || t>up.top())
up.push(t);
else
down.push(t);
if(up.size()-down.size()>=2)
down.push(up.top()), up.pop();
if(down.size()==up.size())
up.push(down.top()), down.pop();
if((i&1)==0)
cout<<up.top()<<" ";
if((i+1)%20==0 && i!=M-1)
cout<<endl;
}
cout<<endl;
}
return 0;
}