动态中位数

动态中位数

依次读入一个整数序列,每当已经读入的整数个数为奇数时,输出已读入的整数构成的序列的中位数。

输入格式

第一行输入一个整数 $P$,代表后面数据集的个数,接下来若干行输入各个数据集。

每个数据集的第一行首先输入一个代表数据集的编号的整数。

然后输入一个整数 $M$,代表数据集中包含数据的个数,$M$ 一定为奇数,数据之间用空格隔开。

数据集的剩余行由数据集的数据构成,每行包含 $10$ 个数据,最后一行数据量可能少于 $10$ 个,数据之间用空格隔开。

输出格式

对于每个数据集,第一行输出两个整数,分别代表数据集的编号以及输出中位数的个数(应为数据个数加一的二分之一),数据之间用空格隔开。

数据集的剩余行由输出的中位数构成,每行包含 $10$ 个数据,最后一行数据量可能少于 $10$ 个,数据之间用空格隔开。

输出中不应该存在空行。

数据范围

$1≤P≤1000$,
$1≤M≤99999$,
所有 $M$ 相加之和不超过 $5×10^5$。

输入样例:

1
2
3
4
5
6
7
8
9
3 
1 9
1 2 3 4 5 6 7 8 9
2 9
9 8 7 6 5 4 3 2 1
3 23
23 41 13 22 -3 24 -31 -11 -8 -7
3 5 103 211 -311 -45 -67 -73 -81 -99
-33 24 56

输出样例:

1
2
3
4
5
6
7
1 5
1 2 3 4 5
2 5
9 8 7 6 5
3 12
23 23 22 22 13 3 5 5 3 -3
-7 -3

解析

动态维护中位数,如果不考虑动态且假设这个数组的长度为 $m$,即离线找一个数组的中位数,就是排序后找数组中下标为 $\left \lfloor \frac{m + 1}{2} \right \rfloor$ 的数。

左边都是小于等于中位数的数,右边都是大于等于中位数的数,一边读取一边动态维护,很显然,左边我们用大根堆维护,右边我们用小根堆维护,只要保证左边的总数为 $\left \lfloor \frac{m}{2}\right \rfloor$,右边的总数为 $\left \lfloor \frac{m + 1}{2} \right \rfloor$ ,那么我们的中位数永远是小根堆的顶端

代码如下

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
//可以不用手搓二叉树,用优先队列 std::priority_queue 也可解决
//std::priority_queue<int, std::vector<int>, std::greater<int> > 为小根堆
//std::priority_queue<int> 为大根堆

const int N = 100005;
int arr[N], bigtree[N], smalltree[N];

//b 开头为大根堆, s 开头为小根堆
int btnt, stnt;
void bup(int s) {
while(s > 1) {
if(bigtree[s / 2] < bigtree[s]) {
std::swap(bigtree[s], bigtree[s / 2]);
s = s / 2;
} else break;
} return;
}

void bdown(int s) {
int t = s * 2;
while(t <= btnt) {
if(t < btnt && bigtree[t] < bigtree[t + 1]) t++;
if(bigtree[s] < bigtree[t]) {
std::swap(bigtree[s], bigtree[t]);
s = t;
t = s * 2;
} else break;
} return;
}

void sdown(int s) {
int t = s * 2;
while(t <= stnt) {
if(t < stnt && smalltree[t] > smalltree[t + 1]) t++;
if(smalltree[s] > smalltree[t]) {
std::swap(smalltree[s], smalltree[t]);
s = t;
t = s * 2;
} else break;
} return;
}

void sup(int s) {
while(s > 1) {
if(smalltree[s / 2] > smalltree[s]) {
std::swap(smalltree[s], smalltree[s / 2]);
s = s / 2;
} else break;
} return;
}

int bGetTop() { return bigtree[1]; }
int sGetTop() { return smalltree[1]; }

void bInsert(int val) {
btnt += 1;
bigtree[btnt] = val;
bup(btnt);
}

void sInsert(int val) {
stnt += 1;
smalltree[stnt] = val;
sup(stnt);
}

void bExtract() {
bigtree[1] = bigtree[btnt--];
bdown(1);
}

void sExtract() {
smalltree[1] = smalltree[stnt--];
sdown(1);
}

int main() {
int T, tot;
scanf("%d", &T);
while(T--) {
memset(arr, 0, sizeof(arr)); stnt = 0, btnt = 0, tot = 0;
int m, n;
scanf("%d %d", &m, &n);
printf("%d %d\n", m, (n + 1) >> 1);
for (int i = 1; i <= n; i++) {
scanf("%d", &arr[i]);
if(stnt == 0) sInsert(arr[i]);
else {
if(arr[i] > sGetTop()) sInsert(arr[i]);
else bInsert(arr[i]);

//这里注意条件,看不明白去看上面的解析
if(btnt > stnt) { sInsert(bGetTop()); bExtract(); }
if(btnt + 1 < stnt) { bInsert(sGetTop()); sExtract(); }
} if(i & 1) { tot++; printf("%d ", sGetTop()); }
//如果为奇数就输出,注意每行10个的条件,且注意 数据会卡tot正好为10的时候
if(tot == 10) { puts(""); tot = 0; }
} if(tot != 0) puts("");
} return 0;
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!