[洛谷 3871][TJOI2010]中位数

题目链接

https://www.luogu.org/problem/P3871

题解

我们建立两个堆，一个大根堆，一个小根堆，且小根堆内的所有元素都比大根堆的元素要大。

刚开始把所有元素都插入同一个堆中。

每次要求中位数的时候，我们从元素较多的堆中取出几个元素，放入元素较少的堆中，直到大根堆有至少一半的元素为止，此时大根堆堆顶即为中位数的值。

插入一个数的时候，我们将这个数与大根堆堆顶作比较，如果比堆顶小则插入大根堆，否则插入小根堆。这样我们就能确保小根堆内的所有元素都比大根堆的元素要大了。

#include <cstdio>
#include <queue>
using namespace std;
priority_queue<int> q1;
priority_queue<int,vector<int>,greater<int> > q2;
int siz1,siz2;
char s[5];
int main()
{
 int n;
 scanf("%d",&n);
 for(int i=1;i<=n;i++)
 {
  int x;
  scanf("%d",&x);
  q1.push(x);
 }
 siz1=n;
 int q;
 scanf("%d",&q);
 while(q--)
 {
  scanf("%s",s);
  if(s[0]=='a')
  {
   int x;
   scanf("%d",&x);
   if(x<=q1.top())q1.push(x),siz1++;
   else q2.push(x),siz2++;
  }
  else
  {
   while(siz1>siz2)
   {
    q2.push(q1.top());
    q1.pop();
    siz1--,siz2++;
   }
   while(siz1<siz2)
   {
    q1.push(q2.top());
    q2.pop();
    siz2--,siz1++;
   }
   printf("%d\n",q1.top());
  }
 }
 return 0;
}