M21509:序列的中位数

heap, http://cs101.openjudge.cn/practice/21509

给出一个长度为N的非负整数序列A，对于所有1≤k≤(N+1)/2，输出A1, A1∼A3, …, A1∼A2k−1的中位数。即前1,3,5,...个数的中位数。中位数是指将一组数据从小到大排列后，位于中间的那个数。

输入

第1行为一个正整数N，表示了序列长度。第2行包含N个非负整数Ai(Ai ≤ 109)。

输出

共(N+1)/2行，分别为前1,3,5,...个数的中位数。

样例输入

7
1 3 5 7 9 11 6

样例输出

提示

对于20%的数据，N ≤ 100；对于40%的数据，N ≤ 3000；对于100%的数据，N ≤ 100000;

python

import heapq
import sys

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    A = list(map(int, data[1:1+n]))
    
    lo = []  # max-heap: store negative values
    hi = []  # min-heap
    
    result = []
    
    for i, num in enumerate(A):
        # Push to lo first
        heapq.heappush(lo, -num)
        
        # Move the largest in lo to hi to maintain order
        heapq.heappush(hi, -heapq.heappop(lo))
        
        # If hi has more elements, move smallest back to lo
        if len(hi) > len(lo):
            heapq.heappush(lo, -heapq.heappop(hi))
        
        # After processing odd number of elements (1st, 3rd, 5th, ...)
        if i % 2 == 0:  # 0-indexed: i=0 -> 1 element, i=2 -> 3 elements, etc.
            median = -lo[0]
            result.append(str(median))
    
    print("\n".join(result))

if __name__ == "__main__":
    main()

M21509:序列的中位数 ​

M21509:序列的中位数