NC50940 Running Median

对顶堆
用一个最大堆和一个最小堆，如果当前元素比最小堆堆顶的值大就插入最小堆，反之插入最大堆。维护最大堆和最小堆的元素差不超过一，如果超过，哪个堆的元素多就把这个堆的堆顶元素给另外一个堆

#include <iostream>
#include <queue>
using namespace std;
int t, num1, num2, x;
int read() {
    char ch;
    int sum, sign = 1;
    while ((ch = getchar()) > '9' || ch < '0')
        if (ch == '-')
            sign = -1;
    sum = ch - '0';
    while ((ch = getchar()) >= '0' && ch <= '9')
        sum = (sum << 3) + (sum << 1) + ch - '0';
    return sum * sign;
}
int main()
{
       t=read();
    while (t--) {
        num1=read();
        num2=read();
        cout << num1 << " " << (num2 + 1) / 2 << endl;
        priority_queue<int,vector<int> ,greater<int> >q1;
        priority_queue<int, vector<int>, less<int> >q2;
        x=read();
        cout << x << " ";
        q1.push(x);
        for (int i = 2; i <= num2; i++) {
            x=read();
            if (q1.top() >= x) {
                q2.push(x);
            }
            else {
                q1.push(x);
            }
            if (q1.size() > 1+q2.size()) {//注意不能写为q1.size()-q2.size()>1 这样写vector会越界（不知道原因emm
                q2.push(q1.top());
                q1.pop();
            }
            else if (q2.size()  > 1+q1.size()) {//这个也要注意
                q1.push(q2.top());
                q2.pop();
            }
            if (i % 2 == 1) {
                if (q1.size() > q2.size())cout << q1.top() << " ";
                else cout << q2.top() << " ";
            }
            if (i % 20 == 0) {
                cout << endl;
            }
        }
        cout << endl;
    }
}