洛谷P1168-中位数

wwww事实上这是我第一次真正接触到堆相关的东西…

题意概括

给出一个长度为N的非负整数序列Ai,对于所有1≤k≤(N+1)/2,输出A1,A1∼A3,…,A1∼A2k−1的中位数。即前1,3,5,…个数的中位数。

题目分析

不难想到,每次查询中位数时,我们可以将当前的数列分为两部分,一部分是比中位数大的数,另一部分是比中位数小的数(由于限定数列长度为奇数,因此中位数一定是某个特定的数而不是某两个数的平均数)。那么假设我们现在已经划分出了一堆比中位数要大的数,又划分出了一堆比中位数小的数。而此时,为了方便起见,我们应当将中位数也划入其中一堆中,这样当两堆数里数的个数差值为1时,多出来的那一个数就是我们要找的中位数了。根据个人习惯,笔者这里首先考虑将中位数放到了比中位数大的那一堆数中。此时,较大的数中最小的那一个就是中位数。现在我们需要新加入一个数,那么此时我们就面临两种情况:

  • 该数比中位数小,我们应当将其划分到比中位数小的那一堆中去。
  • 该数比中位数大,我们应当将其划分到比中位数大的那一堆中去。

对于第一种情况,我们直接将其放到比中位数小的那一堆里即可。

对于第二种情况,我们同理,直接将其放入比中位数大的那一堆里即可。

此时我们又面临三种情况了:

  • 两堆数量相等,此时根据题目条件,不需要输出中位数。
  • 两堆数量相差1,此时根据上述分析,我们输出多出来的那个数即为答案。
  • 两堆数量相差大于1,此时为了平衡两堆数,若较大数的堆里数更多,将其中最小的放到最小堆里即可;若较小数的堆里数更多,将其中最大的数放到最大堆里即可。这样,多出来的那一个数仍然是中位数。

维护一堆数的最大值/最小值,随时需要增加、减少其中的元素,这样的条件很难不让人想到使用堆来完成。但是堆太难写了,于是这里我们考虑使用优先队列来做。

1
priority_queue<int> q;//定义一个优先队列

优先队列本身就是一个大根堆,即其头元素是队列中最大的元素。

1
2
3
4
q.size();//获取q的大小
q.top();//获取q的头元素
q.pop();//弹出(删除)q的头元素
q.push(x);//在q的队尾添加一个x

注:优先队列的坑点,若定义了两个优先队列a、b,使用a.size()-b.size(),其结果会是一个奇奇怪怪的数,原因不明,期待大佬解答。

代码

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
#include <bits/stdc++.h>
using namespace std;

inline int read() {
register char c = getchar();
register int f = 1, _ = 0;
while (c > '9' || c < '0')
f = (c == '-') ? -1 : 1, c = getchar();
while (c <= '9' && c >= '0')
_ = (_ << 3) + (_ << 1) + (c ^ 48), c = getchar();
return _ * f;
}
priority_queue<int> a, b;
int n;

signed main() {
n = read();
for (register int i = 1; i <= n; i++) {
int temp = read();
if (a.empty()) {
a.push(-temp);
} else if (temp > -a.top()) {
a.push(-temp);
} else {
b.push(temp);
}
while (a.size() > 1 + b.size()) {
temp = -a.top();
a.pop();
b.push(temp);
}
while (b.size() > 1 + a.size()) {
temp = b.top();
b.pop();
a.push(-temp);
}
if (i % 2 == 1) {
if (a.size() > b.size())
printf("%d\n", -a.top());
else
printf("%d\n", b.top());
}
}
return 0;
}