题解 洛谷 P1168 中位数

由于这道题目比较水，所以机房中诞生了四种做法，分别是权值线段树、堆、二分以及 $\operatorname{multiset}$。

这里主要介绍本题的堆解法

通过读题我们可以轻易发现，每两次插入数据就需要进行一次访问，且期间必须维护当前访问过的所有元素组成的数列具有单调性 。

问题一：如何维护数列的单调性

于是我们很容易想到可以使用优先队列对其插入的数字进行动态排序来维护其单调性。如果你不知道什么是优先队列，那么不妨先通过下面的传送门去看一看优先队列的用法：
点我

于是你现在明白了什么是优先队列，我们只需要在维护好的单调队列里取出中位数就可以了。所以此时你发现，由于单调队列是一个队列，想要访问中间的元素，就只能把它前面的元素全部弹出来，这样弹出一遍插入一遍甚至不如每次 sort 时间效率高，于是问题来了。

问题二：如何快速地在每次访问中提取中位数

既然我们一定需要把队列分成两段，那么我们直接定义两个优先队列就可以完美地解决问题。我们将前奇数个（这里假设为前 $\mathit{K}$ 个）数列切分后扔进左队列、右队列和中位数三种位置，那么左边的队列维护第 $ 1 $ ~ $\left[\frac{K}{2}\right]$ 个元素，右边的队列维护第 $(\left[\frac{K}{2}\right]+2)$ ~ $K$ 个元素，第$(\left[\frac{K}{2}\right]+1)$ 个元素也就是剩下的那个元素就是中位数，将其定义为 mid 。左边的队列从大到小，使用大根堆，右边的队列从小到大，使用小根堆，定义如下：

1
2
3
4
typedef long long LL;
priority_queue<LL,vector<LL>,greater<LL> > Right;
priority_queue<LL,vector<LL>,less<LL> > Left;
LL mid;

接下来在每个奇数次插入时，如果插入的数比 mid 小，就塞进左队列，如果比 mid 大，就塞进右队列。需要注意的是：为了确保 mid 就是中位数，必须在每次访问时对两个队列内的元素个数进行平衡！ 所以这是最后一个问题。

问题三：平衡两个队列内的元素个数

我们不妨设其中一个队列元素个数为 $x$ ，另一个队列元素个数为 $y$，设 $x>y$ ，则从 $x$ 队列中转移到 $y$ 队列中的元素个数为 $(\frac{x-y}{2}-1)$ 个，最后只需要把 mid 插入到 $y$ 中，再将 $x$ 的队头元素弹出来更新为新的 mid 即可。注意：这一步操作必须先进行当前步骤的插入再进行元素个数平衡。

至此，我们已经解决了这个题目的所有小问题，下面是AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;

namespace SHAWN{
    //定义部分不解释
	typedef long long LL;
	priority_queue<LL,vector<LL>,greater<LL> > Right;
	priority_queue<LL,vector<LL>,less<LL> > Left;
	LL n,mid=0;

	int main()
	{
		cin>>n;//读入n并进行n次插入
		for(LL i=1,x;i<=n;i++){
			cin>>x;
			if(i==1){//i=1的情况边界易出错，所以做一个特判
				mid=x;
				cout<<mid<<"\n";
				continue;
			}
			if(x<=mid) Left.push(x);
			else if(x>mid) Right.push(x);
			if(i&1){//当插入次数为奇数时进行一次平衡和查询
                //定义左右队列的大小
				LL llen=Left.size(),rlen=Right.size();
				if(llen<rlen){//如果左队列个数比右队列个数少
					Left.push(mid);//将中位数进行转移
					LL cha=(rlen-llen)/2;//计算转移数量
					for(int j=1;i<cha;j++){//循环进行转移
						LL tmp=Right.top();
						Left.push(tmp);
						Right.pop();
					}
					mid=Right.top();//更新中位数
					Right.pop();
				}
				else if(llen>rlen){//如果右队列个数比左队列个数少
					Right.push(mid);//将中位数进行转移
					LL cha=(llen-rlen)/2;//计算转移数量
					for(int j=1;i<cha;j++){//循环进行转移
						LL tmp=Left.top();
						Right.push(tmp);
						Left.pop();
					}
					mid=Left.top();//更新中位数
					Left.pop();
				}
				cout<<mid<<"\n";//操作完成后输出中位数
			}
			else continue;//插入次数为偶数次时直接跳过平衡过程
		}
		return 0;
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	return SHAWN::main();
}

以上，如果有不对的地方，还请各位大佬指正！

说些什么吧！

twikoo