SSOJ4174动态维护中位数
909+
作者：crxis 发布：2021-05-20 分类：堆
题目大意：有n个数，请问前m个数的中位数是多少？多次询问哦！
题目描述
给出一个长度为N
的非负整数序列Ai，对于所有1≤k≤(N+1)/2，输出A1,A1∼A3,…,A1∼A2k−1的中位数。即前1,3,5,…
个数的中位数。
输入
第1
行为一个正整数N
，表示了序列长度。
第2
行包含N个非负整数Ai(Ai≤109)
。
输出
共(N+1)/2
行，第i行为A1,A3,…,A2k−1
的中位数。
样例输入
7
1 3 5 7 9 11 6
样例输出
1
3
5
6
提示
数据范围：10, 100, 1000, 5000, 8000, 10000, 20000, 30000, 50000, 70000, 100000
解题思路
动态维护中位数即可，对顶堆经典题目。
程序实现
暴力优化，二分查找、内存移动：动态维护有序数组，排好序后，中间那个数就是中位数。我们可以使用插入排序，先二分查找插入位置，再将大的元素往后移动一位，最后插入新的数字。
对顶堆：中位数m，左边的数字都不大于m，右边的数字都不小于m。只要发现左边的最大值大于右边的最小值，我们就可以将左边的元素，放到右边去。维护最大最小值，我们可以使用堆或者优先队列。对于新进来的数字，小的放左边，大的放右边，为了避免判空，先放左边，再移动到右边也行。接着维护数量，要求左边的不少于右边的，且至多比右边多1个。
