题解 | #Running Median#
Running Median
https://ac.nowcoder.com/acm/problem/50940
使用对顶堆可解，左边的堆维护中位数前半部分，右边的堆维护中位数后半部分。在新的数进来的时候判断应该插左边还是右边，然后对左右如果差值超过1进行调整。
这样要么左堆的顶端是中位数，要么当左右相同大小的时候就是两个堆顶的数取平均数。
//对顶堆，以左边为承载多出来的那个中间数的堆
#include <bits/stdc++.h>
using namespace std;
int p;
int main() {
cin>>p;
while (p--) {
priority_queue<int, vector<int>, less<int> > zuo;
priority_queue<int, vector<int>, greater<int> > you;
int num, m, val;
cin>>num>>m;
vector<int> v;
for (int i=1;i<=m;i++) {
cin>>val;
if (zuo.size()==you.size()) {
if (zuo.size()==0) {
zuo.push(val);
} else if (you.top()<val)
{
you.push(val);
zuo.push(you.top());
you.pop();
} else {
zuo.push(val);
}
}else {
if (zuo.top()>=val) {
zuo.push(val);
you.push(zuo.top());
zuo.pop();
} else {
you.push(val);
}
}
if (i&1==1) {
if (!zuo.empty()) {
if (zuo.size()==you.size()) v.push_back((zuo.top()+you.top())/2);
else v.push_back(zuo.top());
}
}
}
cout<<num<<" "<<v.size()<<endl;
int i;
for (i=0;i<v.size();i++) {
cout<<v[i]<<" ";
if ((i+1)%10==0) {
cout<<endl;
}
}
if (i%10!=0)
cout<<endl;
}
return 0;
}
三环集团开奖34人在聊