【题解】序列合并之中位数

题意

给你个序列，依次合并这个序列，并且每次输出合并后序列的中位数。

题解

可以考虑用两个堆来维护中位数，即对顶堆，假设中位数为，我们让大根堆中存入所有小于的数，让小根堆中存入所有大于等于的数，即小根堆的堆顶是较大的数中最小的，大根堆的堆顶是较小的数中最大的。将大于大根堆堆顶的数（比所有大根堆中的元素都大）的数放入小根堆，小于等于大根堆堆顶的数（比所有小根堆中的元素都小）的数放入大根堆。那么就保证了所有大根堆中的元素都小于小根堆中的元素。那么我们只要去维护大根堆的元素个数和小根堆的元素个数差值不大于1。元素个数较多的堆的堆顶元素即为当前中位数，如果元素个数相同，那么就是两个堆堆顶元素的平均数。维护方式只用把元素个数多的堆的堆顶元素取出，放入元素个数少的堆即可。
所以对于每次合并序列，我们只用重复上述维护操作即可。合并操作实际上就是入队操作。

复杂度

时间复杂度为

代码

#include <bits/stdc++.h>
using namespace std;
priority_queue<int,vector<int> >Q1;
priority_queue<int,vector<int>,greater<int> >Q2;
int main()
{
    int n;
    scanf("%d",&n);
    int siz=0;
    while(n--)
    {
        int m;
        scanf("%d",&m);
        siz+=m;
        for(int i=0; i<m; i++)
        {
            int x;
            scanf("%d",&x);
            if(!Q1.empty()&&x<=Q1.top())
                Q1.push(x);
            else if(!Q2.empty()&&x>Q2.top())
                Q2.push(x);
            else
                Q2.push(x);
            if(Q1.size()>Q2.size())
            {
                Q2.push(Q1.top());
                Q1.pop();
            }
            else if(Q2.size()>Q1.size()+1)
            {
                Q1.push(Q2.top());
                Q2.pop();
            }
        }
        if(siz%2==1)
            printf("%d\n",Q2.top());
        else
        {
            int ans=Q1.top()+Q2.top();
            ans%2==0?printf("%d\n",ans/2):printf("%.1lf\n",ans/2.0);
        }
    }
    return 0;
}