Running Median (中位数)Running Median

93 阅读 0 评论 62 点赞

我是靠谱客的博主自信唇彩，这篇文章主要介绍Running Median (中位数)Running Median，现在分享给大家，希望可以做个参考。

Running Median

问题：给奇数个数( int范围内)，依次输出1~ i (1<=i<=n)内的中位数，i 为奇数。
思路：经典题目？，据说什么主席树（可持久化线段树），红黑树，平衡树 ……都可以解？，不会。
这里用对顶堆解法：开一个大根堆，一个小根堆，依次将数插入两个堆，同时维护大根堆里放的是较小的一半数，小根堆里放的是较大的一半数，当到奇数位置时大根堆堆顶就是中位数。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>
using namespace std;
int main()
{
int T;
scanf("%d",&T);
while(T--){
int t,n,x,num=0;
scanf("%d%d",&t,&n);
priority_queue<int> Q1;
//大根堆，存较小的那一半数
priority_queue<int,vector<int>,greater<int> > Q2;	//小根堆，存较大的那一半数
for(int i=1;i<=n;i++){
if(i==1) printf("%d %dn",t,(n+1)/2);
scanf("%d",&x);
if(i&1) Q1.push(x);
else Q2.push(x);
if(i>=2){
int a= Q1.top(),b = Q2.top();
if(a>b){
//保证Q1中的数小于或等于Q2中的数
Q1.pop(),Q2.pop();
Q1.push(b),Q2.push(a);
}
}
if(i&1) printf("%d ",Q1.top());
if(i%20==0) printf("n");
}
printf("n");
}
return 0;
}