「Luogu 1168」中位数

题目大意：给出一个长度为 $N$ 的非负整数序列 $A_i$，对于所有 $1≤k≤(N+1)/2$，输出 $A_1,A_3,…,A_{2k-1}$ 的中位数。即前 $1,3,5,…$ 个数的中位数。$N≤100000$

开一个大根堆和一个小根堆，将当前序列的全部元素放入这两个堆中，然后维护下面两条性质：

• 大根堆里的元素个数比小根堆多一
• 大根堆的堆顶元素比小根堆的堆顶元素小

设当前序列的长度为 $n$，那么大根堆里的元素就是前 $\lfloor\dfrac{n+1}{2}\rfloor$ 小的数，小根堆里的元素是后 $\lfloor\dfrac{n}{2}\rfloor$ 小的数，因此大根堆的堆顶元素就是当前序列的中位数。

#include <cstdio>
#include <queue>

std::priority_queue<int> Q1; //大根堆
std::priority_queue<int, vector<int>, greater<int> > Q2; //小根堆

int read() {
    int x = 0; char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    while (c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    return x;
}

int main() {
    int n = read(), x = read();
    Q1.push(x); printf("%d\n", x);
    for (int i = 3; i <= n; i += 2) {
        int x = read(), y = read();
        if (x > y) x ^= y, y ^= x, x ^= y;
        Q1.push(x), Q2.push(y);
        if (Q1.top() > Q2.top()) {
            x = Q1.top(), y = Q2.top();
            Q1.pop(), Q1.push(y);
            Q2.pop(), Q2.push(x);
        }
        printf("%d\n", Q1.top());
    }
    return 0;
}

时间复杂度 $O(n \log n)$