E5-D 中位数

题目描述

Bellalabella 学到了中位数的知识，Bellalabella 想知道对于一个长度为 nn 的序列 a1,a2,…,ana_1,a_2,…,a_n，所有前缀的中位数是多少。

由于 Bellalabella 学艺不精，不知道长度为偶数的序列的中位数的定义，因此她只需要你求出长度为奇数的所有前缀的中位数。

一个长度为 2n−12n−1 的序列的中位数是将这个序列从小到大排序后第 n 个位置的数，例如$ [1,3,2]$ 中位数为 2，[2,3,2]2，[2,3,2] 中位数为 22。

输入格式

第一行一个正整数 t（1≤t≤10）t（1≤t≤10），表示数据组数。

对于每组数据，第一行一个正奇数 n（1≤n≤105）n（1≤n≤10^5），含义同题目描述。

第二行 nn 个整数 a1,a2,…,an（0≤ai≤105）a_1,a_2,…,a_n（0≤a_i≤10^5），含义同题目描述。

对于得分占比 50%50\% 的测试点，保证 0≤ai≤200≤a_i≤20。

输出格式

对于每组数据，输出一行 n+12\frac{n+1}2 个整数，第 ii 个数表示长度为 $2i−1 $的前缀的中位数。

输入样例

1
2
3
4
5
2
5
3 4 5 1 2
13
13 25 19 11 29 19 17 17 5 9 11 11 3

输出样例

1
2
3 4 3
13 19 19 19 17 17 13

题目分析

根据题目易得，当前输入的数有奇数个时才输出中位数。对于每次输出，都需要将数字按从小到大排序，但是我们只需要中间的数。

所以考虑将所有数分为三块，一块比中位数小(AA块)，一块比中位数大(BB块)，一个中位数(midmid)。

每次加入数字时与中位数比较，再加入不同块。当数字总数为奇数个时，判断非中位数块哪边数更多。如果AA块数更多，则取其中最大的数作为中位数；BB块数更多则取其中最小的数。同时维护两块中数字个数相等。

由于AA块只需要最大的数所以考虑使用大顶堆来存储，同理BB块使用小顶堆。

示例代码

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
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        int n, mid, a;
        priority_queue<int, vector<int>, less<int>> B;
        priority_queue<int, vector<int>, greater<int>> A;
        cin >> n;
        scanf("%d", &a);
        mid = a;
        cout << mid << " ";
        for (int i = 2; i <= n; i++)
        {
            scanf("%d", &a);
            if (a > mid)
                A.push(a);
            else
                B.push(a);
            if (i % 2 == 1)
            {
                if(A.size()>B.size())
                {
                    B.push(mid);
                	mid = A.top();
                    A.pop();
				}
                else if(A.size()<B.size())
                {
                    A.push(mid);
                	mid = B.top();
                    B.pop();
				}
                cout << mid << " ";
            }
        }
        cout << endl;
    }
    return 0;
}