[刷题笔记] Luogu P1168 中位数

Problem

Description

题目描述非常简洁，不作解释。

Solution

题目要求对前奇数项求中位数？朴素的做法是暴力，但是范围1e5显然T。这里主要介绍一种堆顶堆的做法。

堆顶堆是什么呢？我们不妨开两个堆，一个大根堆一个小根堆。动态维护中位数，初始令前1位的中位数为\(a_i\)，遍历数组，若遇到比中位数\(m\)小的数则放到大根堆，否则放到小根堆。

我们发现，若大根堆内的元素数=小根堆内的元素数时，\(m\)恰好为此时的中位数。若不满足呢？分类讨论一下：

• 若大根堆内元素数 > 小根堆内元素数，则此时的中位数为大根堆堆顶，把原来的\(m\)放到小根堆。
• 反之则中位数肯定在小根堆，把原来的\(m\)放到大根堆，小根堆堆顶为\(m\)

我们发现，每次遍历到奇数时，进行上述操作使两个堆平衡，平衡完的\(m\)显然就是此时的中位数。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#define N 100010
using namespace std;
priority_queue <int> q1; //开大根堆和小根堆
priority_queue<int,vector<int>,greater<int> >q2;
int mid;
int n;
int a[N];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	mid = a[1];
	cout<<mid<<endl;
	for(int i=2;i<=n;i++)
	{
		if(a[i] > mid) q2.push(a[i]);
		else q1.push(a[i]);
		if(i%2 == 1)
		{
			while(q1.size() != q2.size()) //查询到奇数动态平衡
			{
				if(q1.size() > q2.size()) 
				{
					q2.push(mid);
					mid = q1.top();
					q1.pop();
				}
				else
				{
					q1.push(mid);
					mid = q2.top();
					q2.pop();
				}
			}
			cout<<mid<<endl;	
		}
	}
}