27947: 动态中位数

http://cs101.openjudge.cn/practice/27947/

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

输入

第一行输入一个整数 T（1<=T<=100），代表后面数据集的个数。接下来每行一个数据集，包含 M 个空格分隔的整数。1<=M<=99999 且所有 M 相加之和不超过500000。

输出

对于每个数据集输出两行，第一行输出中位数的个数N。

第二行输出空格分隔的N个整数，表示中位数。

样例输入

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

样例输出

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

提示

tags: heap

来源

AcWing 106, https://www.acwing.com/problem/content/description/108/

python

import heapq

def dynamic_median(nums):
    # 维护小根和大根堆（对顶），保持中位数在大根堆的顶部
    min_heap = []  # 存储较大的一半元素，使用最小堆
    max_heap = []  # 存储较小的一半元素，使用最大堆

    median = []
    for i, num in enumerate(nums):
        # 根据当前元素的大小将其插入到对应的堆中
        if not max_heap or num <= -max_heap[0]:
            heapq.heappush(max_heap, -num)
        else:
            heapq.heappush(min_heap, num)

        # 调整两个堆的大小差，使其不超过 1
        if len(max_heap) - len(min_heap) > 1:
            heapq.heappush(min_heap, -heapq.heappop(max_heap))
        elif len(min_heap) > len(max_heap):
            heapq.heappush(max_heap, -heapq.heappop(min_heap))

        if i % 2 == 0:
            median.append(-max_heap[0])

    return median

T = int(input())
for _ in range(T):
    #M = int(input())
    nums = list(map(int, input().split()))
    median = dynamic_median(nums)
    print(len(median))
    print(*median)

27947: 动态中位数 ​

27947: 动态中位数