题面
题目要求动态维护中位数, 每当序列长为奇数时输出(也就是输出第i/2+1小的数).
设当前序列长为i, 我们把整个序列按升序分为第1~i/2小, 第i/2+1小两部分.
资瓷动态插入并维持有序的数据结构容易想到堆. 对左半边和右半边分别开一个大根堆left 小根堆right, 那么right.top()即为中位数.
每次加入一个数x, 若比当前中位数大就push到right里面, 否则push到left里面.
为了保证左边右边各占总序列的一半, 每次插入数后都要检查, 若left里面多了一个数, 就把left.top()弹到right里面, 也就是把左边序列最大的一个数移到右边序列, 在保证有序的同时保证了左右各占一半.right多了同理.
STL优先队列默认是大根堆, 重载小于号比较麻烦, 有一个妙不可言的方法: 取每个数的相反数放入堆中, 取出来的时候再取一次相反数, 这样就变成了小根堆.
展开代码
#include<cstdio>
#include<queue>
#define in inline
#define re register
using namespace std;
in int read()
{
int s(0),b(0);char ch;
do{ch=getchar();if(ch=='-')b=1;}while(ch<'0'||ch>'9');
while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
if(b) return -s;
return s;
}
int n;
priority_queue<int> left,right;
signed main()
{
int T=read();
while(T--)
{
int num=read();
n=read();
printf("%d %d\n",num,n/2+1);
int cnt=0;
for(re int i=1;i<=n;++i)
{
int x=read();
if(i==1) right.push(-x);
else
{
if(x<-right.top()) left.push(x);
else right.push(-x);
}
if(right.size()>i/2){left.push(-right.top());right.pop();}
if(left.size()>i/2){right.push(-left.top());left.pop();}
if(i&1){printf("%d ",-right.top());++cnt;if(cnt%10==0) printf("\n");}
}
if(cnt%10) printf("\n");
while(!left.empty()) left.pop();
while(!right.empty()) right.pop();
}
return 0;
}