洛谷P1168 中位数 题解

题目链接：P1168 中位数

题意：

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

数据范围：

对于$100\%$的数据，$N ≤ 100000$。

当然可以用vector来搞啦，但是这样就常数大而且没劲了

考虑对顶堆（那篇讲对顶堆的是在绕口令吧。明明很好懂的）

维护两个堆，分别是大根堆和小根堆

有个性质：大根堆q1里的所有值小于小根堆q2里的所有值

然后每次把比q1堆首元素大的元素扔到q2里去，反之塞进q1里

这样还是满足性质的

但是我们要中位数，这就需要q1和q2的size只相差一，才好处理

怎么搞呢，比如q1的size太大了，那我们就把q1的堆首一个个扔到q2里去

这样仍然是满足性质的

注意到每个元素最多入堆2次，因此单次插入操作是 $O(\log n)$ 的

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

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
#include <queue>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)()

int n;
priority_queue<int> q1;
priority_queue<int,vector<int>,greater<int>>q2;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    int x; cin >> x;
    q1.push(x); cout << x << '\n';
    for(int i=2; i<=n; i++)
    {
        cin >> x;
        if(x>q1.top())q2.push(x);
        else q1.push(x);
        while(abs((int)(q1.size()-q2.size()))>1)
        {
            if(q1.size()>q2.size())
                q2.push(q1.top()),q1.pop();
            else q1.push(q2.top()),q2.pop();
        }
        if(i&1) cout << (q1.size()>q2.size()?q1.top():q2.top()) << '\n';
    }
    return 0;
}