20200409 Running Median

题意翻译

输入 个数，每次到奇数个数的时候输出中位数。

多测， 组数据。

题解

使用对顶堆。

一个小根堆，存放比中位数大的数。

一个大根堆，存放比中位数小的数。

动态调整堆的大小。

参考了神仙的 std 写法，细节处理比我之前的写法好的多。

priority_queue 的坑点

  • priority_queue < int, vector < int >, greater < int > > 可以直接定义小根堆

  • priority_queue 的成员函数 size 返回类型为 unsigned int 型，如果直接在 if 的条件中调用 size 函数并进行运算，一定要写 (int)q.size()

code

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;

template < typename Tp >
void read(Tp &x) {
    x = 0; int fh = 1; char ch = 1;
    while(ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
    if(ch == '-') fh = -1, ch = getchar();
    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    x *= fh;
}

int T, n;

void Init(void) {
    read(T);
}

priority_queue <int> q1;
priority_queue <int, vector < int >, greater < int > > q2;

void solve(void){

    while(q1.size()) q1.pop();
    while(q2.size()) q2.pop();

    int cas;
    read(cas);read(n);

    printf("%d %d\n", cas, (n + 1) / 2);

    read(cas);
    q1.push(cas);
    printf("%d ", cas);
    for(int i = 2, x; i <= n; i++) {
        read(x);
        if(x <= q1.top()) q1.push(x);
        else q2.push(x);
    //    printf("\n %d - 1  ** q1 = %d, q2 = %d \n", i, q1.size(), q2.size());
        if((int)q1.size() - (int)q2.size() > 1) {
            q2.push(q1.top()); q1.pop();
        }
        else if((int)q2.size() - (int)q1.size() > 1) {
            q1.push(q2.top()); q2.pop();
        }

//        printf("\n %d - 2  ** q1 = %d, q2 = %d \n", i, q1.size(), q2.size());

        if(i % 2 == 1) {
            if((int)q1.size() > (int)q2.size()) printf("%d ", q1.top());
            else printf("%d ", q2.top());
            if(i % 20 == 19 && i != n) puts("");
        }
    }
    puts("");
}

void Work(void) {
    while(T--) {
        solve();
    }
}

int main(void) {
    Init();
    Work();
    return 0;
}