AcWing-106-动态中位数

问题

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

输入格式

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

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

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

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

输出格式

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

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

输出中不应该存在空行。

数据范围

1≤P≤1000,
1≤M≤9999

输入样例：

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 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

思路

• 题目大意：每读入奇数个整数，输出其中位数。

可以使用一个最大堆和一个最小堆进行数据的存放，排序后的前 1 - M/2 个数放在最大堆，后 M/2+1 - M 个放在

最小堆，则中位数即为最小堆的堆顶元素。

具体流程：

开始的时候，将第一个元素插入最小堆。

之后，每读入一个数，判断其与最小堆的堆顶的大小，小则插入最大堆，否则插入最小堆。

在执行插入操作之后，按照思路，最大堆和最小堆的数量要么相等，要么最小堆比最大堆朵一。若最小堆的元素数量比最大堆的元素数量大2，则最小堆的元素多了，需要将最小堆的堆顶元素移到最大堆；若最大堆的元素数量比最小堆的元素数量大1，则最大堆的元素多了，需要将最大堆的堆顶移动到最小堆。

题解

#include<iostream>
#include<cstdio>
#include<queue>

using namespace std;

const int MAX = 1e4;
int a[MAX];
int p, m;

int main() {
    cin >> p;
    int idx, x, cnt;

    priority_queue<int> max_heap;
    priority_queue<int, vector<int>, greater<int>> min_heap;

    for (int i = 0; i < p; ++i) {
        cin >> idx >> m;
        cout << idx << " " << m / 2 + 1 << endl;
        cnt = 0;

        for (int j = 0; j < m; ++j) {
            scanf("%d", &x);
            if (j > 0 && x < min_heap.top()) {
                max_heap.push(x);
                if (max_heap.size() == min_heap.size() + 1) {
                    min_heap.push(max_heap.top());
                    max_heap.pop();
                }
            } else {
                min_heap.push(x);
                if (max_heap.size() + 2 == min_heap.size()) {
                    max_heap.push(min_heap.top());
                    min_heap.pop();
                }
            }

            if (!(j & 1)) { //读入奇数个数时候输出
                if (cnt % 10 == 0 && cnt != 0) cout << endl;
                cout << min_heap.top() << " ";
                cnt++;
            }
        }
        cout << endl;

        max_heap = priority_queue<int>();
        min_heap = priority_queue<int, vector<int>, greater<int>>();
    }

    return 0;
}