洛谷P1168 中位数

题目描述

给定一个长度为 $N$ 的非负整数序列 $A$，对于前奇数项求中位数。

输入格式

第一行一个正整数 $N$。

第二行 $N$ 个正整数 $A_{1\dots N}$。

输出格式

共 $\lfloor \frac{N + 1}2\rfloor$ 行，第 $i$ 行为 $A_{1\dots 2i - 1}$ 的中位数。

样例 #1

样例输入 #1

7
1 3 5 7 9 11 6

样例输出 #1

1
3
5
6

样例 #2

样例输入 #2

7
3 1 5 9 8 7 6

样例输出 #2

3
3
5
6

提示

对于 $20\%$ 的数据，$N \le 100$；

对于 $40\%$ 的数据，$N \le 3000$；

对于 $100\%$ 的数据，$1 \le N ≤ 100000$，$0 \le A_i \le 10^9$。

题解

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

priority_queue<int, vector<int>> big;               // 大根堆
priority_queue<int, vector<int>, greater<int>> sma; // 小根堆

int absf(int x) {
    if (x >= 0)
        return x;
    else
        return -x;
}

int n, t;

int main() {
    cin >> n;
    scanf("%d", &t);
    big.push(t);
    cout << big.top() << endl;
    for (int i = 2; i <= n; i++) {
        scanf("%d", &t);
        if (t > big.top())
            sma.push(t);
        else
            big.push(t);
        while (absf(big.size() - sma.size()) > 1) {
            if (big.size() > sma.size()) {
                sma.push(big.top());
                big.pop();
            } else {
                big.push(sma.top());
                sma.pop();
            }
        }
        if (i % 2 != 0) {
            if (big.size() > sma.size())
                printf("%d\n", big.top());
            else
                printf("%d\n", sma.top());
        }
    }
    return 0;
}