题目如题

• 数据结构的选取：
  我们知道中位数是一个有序序列最中间的元素值。那么，用来保存输入的值数据结构应该带自动排序的功能。
  显然，二叉堆具有这样的特点。结合中位数的特点，显然，在中位数的位置把一个有序的序列分成两段。
  分别保存在两个二叉堆中。一个二叉堆的堆顶是最大元素，一个二叉堆的堆顶是最小元素。这样就可以
  把中位数给找出来。最终，确定要使用两个二叉堆，用一个大顶堆，一个小顶堆互相配合，
  可以动态输出中位数。

• 数据结构的维护：
  大顶堆的堆顶元素必须不大于小顶堆的堆顶元素。这是因为，这两个堆里面的元素必须能构成一个有序序列。
  当输入的值破坏这个规则的时候，两个堆的堆顶元素交换。
  假设大顶堆中的元素个数为s1，小顶堆中的元素个数为s2。
  那么必然有：s1 + s2 = 2k或者s1 + s2 = 2k + 1(k = 0, 1, 2, . . . , n)
  当s1 + s2 = 2k时，s1 <= s2
  当s1 + s2 = 2k + 1时，s1 <= s2 + 1
  否则，s1 > s2或者s1 > s2 + 1的时候，就要将大顶堆的堆顶元素推入小顶堆中。
  即s1 > s2 + 1 （求不等式解集，哈哈。看到了数学影子。）

C++ 代码

#include <iostream>
#include <queue>
using namespace std;
int t, n, m;
priority_queue<int> max_heap;
priority_queue<int, vector<int>, greater<int>> min_heap;

int main() {

    cin >> t;
    while(t--) {
        cin >> n >> m;
        cout << n << " " << (m + 1) / 2 << endl;
        int cnt = 0;
        for(int i = 0, x; i < m; i++) {
            cin >> x;
            max_heap.push(x);
            // 规则1：保证大顶堆堆顶小于小顶堆堆顶始终成立。
            //        否则，交换它们的堆顶
            if(min_heap.empty()) {
                if(max_heap.top() > min_heap.top()) {
                    auto a = min_heap.top(), b = max_heap.top();
                    min_heap.pop(), max_heap.pop();
                    min_heap.push(b), max_heap.push(a);
                }
            }
            // 规则2：s1 + s2 = 2k 或 s1 + s2 = 2k + 1
            //        s1 <= s2 或者 s1 <= s2 + 1 即s1 <= s2 + 1
            //        保证s1 <= s2 + 1 始终成立
            //        否则，大顶堆堆顶压入小顶堆堆顶
            if(max_heap.size() > min_heap.size() + 1) {
                min_heap.push(max_heap.top());
                max_heap.pop();
            }

            if(i & 1) continue;
            cout << max_heap.top() << " ";
            if(++cnt % 10 == 0) puts("");
        }
        if(cnt % 10 == 0) puts("");
    }
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla