题面大意：输入一串数，每次输入到奇数个数时，输出这奇数个 数的中位数。

戳我传送

• 解前吐槽：

  这个题目本来是水题，随便混都可以A的，不管是sort还是nth_element都可以A，说明原题之水，不过被选来的当每日一题的好题目，我们帅气可爱的牛客运营大大们，直接给题目来了波数据史诗级加强，搞得本人只有去学一下怎么用对顶堆求中位数了。

• 解题思路：

  每输入一个数，判断它是不是比小顶堆堆顶还要小，这样的话就把这个数放到大顶堆中；
  如果这个数大于等于小顶堆堆顶，就插入小顶堆中。
  这样我们就可以保证小顶堆元素中最小的，大于大顶堆中全部的数。
  我们保证数据元素个数奇数的情况下，小顶堆元素个数==大顶堆元素个数+1；这样答案就保存在小顶堆堆顶了。
  一段数据，新插入的数，要么吧中位数前推一位，要么后推一位，要么自己就是中位数，只要保证数据保持有序，那么奇数个数，小根堆size+大根堆size==序列长度，那么小根堆里面最小的那个元素就是原始序列的中位数了。
  这样插入log，n个数要输入，T组；

  总的时间复杂度应该是 O(T * n* log(n))；一开始投机取巧的时间复杂度应该是O(T * n^2)往上走。

我写的程序运行如下
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43385126&returnHomeType=1&uid=919749006

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;

inline int read() {
    int s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}

vector<int> p;

//  保持小根堆中最小元素要大于大根堆中的全部元素

priority_queue<int, vector<int>, greater<int> > q1;//小根堆
priority_queue<int, vector<int>, less<int> > q2;//大根堆

void add(int x) {
    if (q1.empty()) {
        q1.push(x);
        return;
    }
    if (x > q1.top())    q1.push(x);
    else    q2.push(x);
    while (q1.size() < q2.size()) {
        q1.push(q2.top());
        q2.pop();
    }
    while (q1.size() > q2.size() + 1) {
        q2.push(q1.top());
        q1.pop();
    }
}

int main() {
    int T = read();
    while (T--) {
        while (q1.size())   q1.pop();
        while (q2.size())   q2.pop();
        p.clear(); //多组记得清空一下
        int ca = read(), n = read();
        for (int i = 0; i < n; ++i) {
            int x = read();
            add(x);
            if ((i & 1) == 0)   p.push_back(q1.top());
        }
        printf("%d %d\n", ca, (n + 1) >> 1); //中位数个数 +1在偶数的时候不影响
        for (int i = 0; i < p.size(); ++i) {
            printf("%d", p[i]);
            if ((i + 1) % 10 == 0)  puts("");
            else    printf(" ");
        }
        if(p.size()%10) puts(""); //注意特判最后是否有数据，有才回车。。虽然不知道为什么这个点MLE2发
    }
    return 0;
}