Arce 发表于 2021-7-27 13:36:16

P1168 中位数(对顶堆)

题意:维护一个序列,两种操作
1、插入一个数
2、输出中位数(若长度为偶数,输出中间两个较小的那个)
对顶堆
维护一个小根堆,一个大根堆,大根堆存1--mid,小根堆存mid+1---n
这样堆顶必有中位数。
每次操作后维护两个堆元素数量,保证一个比另一个多1或相等
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#define love_nmr 0
#define nmr 100500
priority_queue<int,vector<int>,greater<int> >q;
priority_queue<int>p;
int n;
int m;
int tot1;
char olinr;
int tot2;
int a;
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++)
      cin>>a;
    sort(a+1,a+n+1);
    for(int i=1;i<=(n/2);i++)
    {
      p.push(a);
      tot1++;
    }
    for(int i=(n/2)+1;i<=n;i++)
    {
      q.push(a);
      tot2++;
    }
    cin>>m;
    int x;
    while(m--)
    {
      cin>>(olinr+1);
      if(olinr=='a')
      {
            cin>>x;
            if(x<p.top())
            {
                p.push(x);
                tot1++;
            }
            else
            {
                q.push(x);
                tot2++;
            }
      }
      else
      {
            if(tot2>tot1)
                cout<<q.top()<<endl;
            else
                cout<<min(q.top(),p.top())<<endl;
      }
      while(tot2-1>tot1)
      {
            tot2--;
            tot1++;
            p.push(q.top());
            q.pop();
      }
      while(tot2<tot1)
      {
            tot2++;
            tot1--;
            q.push(p.top());
            p.pop();
      }
    }
    return love_nmr;
}
----olinr


文档来源:51CTO技术博客https://blog.51cto.com/u_15314204/3190979
页: [1]
查看完整版本: P1168 中位数(对顶堆)