刷题记录:牛客NC50940Running Median

传送门:牛客

题目描述:

For this problem, you will write a program that reads in a sequence of 32-bit signed integers. After each 
odd-indexed value is read, output the median (middle value) of the elements received so far.
输入:
3 
1 9 
1 2 3 4 5 6 7 8 9 
2 9 
9 8 7 6 5 4 3 2 1 
3 23 
23 41 13 22 -3 24 -31 -11 -8 -7 
3 5 103 211 -311 -45 -67 -73 -81 -99 
-33 24 56
输出:
1 5
1 2 3 4 5
2 5
9 8 7 6 5
3 12
23 23 22 22 13 3 5 5 3 -3 
-7 -3

首先这道题是一道需要动态求出中位数的一道题,一想到中位数,我们肯定会想到单调性,所以这道题显然是需要使用优先队列来动态的储存我们的数据,但是因为优先队列是无法直接输出队列中的数字的(只能输出队首数字),所以我们单单使用优先队列显然是无法解决这道题的.那么该怎么解决这道中位数的题呢.

我们思考一下,中位数是什么.中位数的前面显然都是比中位数小的,中位数的后面都是比中位数大的,那么假设我们分别存储了较大值和较小值(也就是按大小来平分已经输入的数据),并且如果我们使用单调队列来维护较大值和较小值的话,此时我们输出中位数的值就很简单了

下面是具体实现过程

我们用单调增的队列来维护较大值,用单调减的队列来维护较小值,每次增加一个数,我们就与较大值

队列的队首进行比较(此时较大值队列的队首是队列中的最小值),如果这个数连我们的队首都比不过

的话,我们就将其先放入我们的较小值队列之中,反之,我们将其放入我们的较大值队列之中,但是因为

我们需要找出我们的中位数,所以我们的较大值和较小值的个数应该是尽量平分的,所以我们还要继

续判断两者的个数,将多的一方加入小的一方,这样的话我们就会发现显然个数较多的那一方的队首

就是我们的中位数(较大值的队首是较小的,而较小值的队首的较大的),又因为中位数是奇数时才有

的,所以我们直接输出即可.

PS:注意输出的格式即可

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define maxn 1000000
#define ll_maxn 0x3f3f3f3f3f3f3f3f
const double eps=1e-8;
priority_queue<int>q2;//维护小根堆
priority_queue<int,vector<int>,greater<int> >q1;//维护大根堆
int T;
int main() {
	T=read();int bianhao,n;
	while(T--) {
		while(q1.size()) q1.pop();
		while(q2.size()) q2.pop();
		bianhao=read();n=read();
		int num;int ans=0;
		printf("%d %d\n",bianhao,(n+1)/2);
		for(int i=1;i<=n;i++) {
			num=read(); 
			if(!q1.empty()&&q1.top()>=num) {
				q2.push(num);
			}else {
				q1.push(num);
			}
			if(q1.size()>q2.size()+1) {
				q2.push(q1.top());
				q1.pop();
			}else if(q1.size()+1<q2.size()) {
				q1.push(q2.top());
				q2.pop();
			}
			if(i&1) {
				if(q1.size()>q2.size()) {
					printf("%d ",q1.top());
				}else {
					printf("%d ",q2.top());
				}
			}
			if(i%20==0) printf("\n");
		}
		cout<<endl;
	}
	return 0;
}