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]