洛谷P1168《中位数》

两个优先队列

解析

第一反应肯定是堆,毕竟自带排序,找中位数也方便

关键是 std::priority_queue 不能访问内部元素就很烦

但是,要访问的内部元素好像就一个中位数啊?


考虑把中位数手动记下来,然后把中位数前边的数用一个大根堆存一下,把中位数后面的数用一个小根堆存一下,这样依然能保证元素是始终有序的

依次读入每一个数,如果这个数比「当前记着的中位数」小就放进大根堆里,否则放进小根堆里

查询的时候需要对中位数进行更新:
如果左右两个堆的大小相等,说明中位数还是那个中位数;
否则分两种情况讨论:

  1. 大根堆更大
    说明中位数一定在大根堆里,那么就把中位数塞进小根堆里,再把大根堆堆顶取出来当新的中位数,重复做直到两个堆大小相等
  2. 小根堆更大
    说明中位数一定在小根堆里,那么就把中位数塞进大根堆里,再把小根堆堆顶取出来当新的中位数,重复做直到两个堆大小相等

最后输出更新完的中位数即可

本方法对应代码中的 Method1


或者可以直接使用 std::vectorstd::upper_bound 来模拟一个堆,输出的时候直接访问 vec[(i / 2 + 1) - 1] 即可

std::upper_bound(Begin Iterator, End Iterator, Value) 是一个使用二分查找,在有序序列 [Begin Iterator, End Iterator) 中查找第一个大于 Value 的位置的函数;std::vector<int>::insert(Position Iterator, Value) 可以在 Position Iterator 前面插入元素 Value,利用这两个函数可以实现插入元素而不破坏序列的有序性。

本方法对应代码中的 Method2

代码实现

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
//
// LuoguP1168.cpp
// Title: 中位数
// Debugging
//
// Created by HandwerSTD on 2019/10/2.
// Copyright © 2019 HandwerSTD. All rights reserved.
//

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>

#define FILE_IN(__fname) freopen(__fname, "r", stdin)
#define FILE_OUT(__fname) freopen(__fname, "w", stdout)
#define rap(a,s,t,i) for (int a = s; a <= t; a += i)
#define basketball(a,t,s,i) for (int a = t; a > s; a -= i)
#define countdown(s) while (s --> 0)
#define IMPROVE_IO() std::ios::sync_with_stdio(false)

using std::cin;
using std::cout;
using std::endl;

typedef long long int lli;

int getint() { int x; scanf("%d", &x); return x; }
lli getll() { long long int x; scanf("%lld", &x); return x; }

int n;

namespace Method1 {
/**
* 此题正解
* 用一个大根堆维护中位数之前的数,一个小根堆维护中位数之后的数
*/

std::priority_queue<int> before;
std::priority_queue<int, std::vector<int>, std::greater<int> > after;
int mid;

void _main() {
for (int i = 1; i <= n; ++i) {
int now = getint();
if (i == 1) { mid = now; }
else {
if (now < mid) before.push(now);
else after.push(now);
}
if (i & 1) {
unsigned long befsiz = before.size();
unsigned long aftsiz = after.size();
while (befsiz != aftsiz) {
if (befsiz < aftsiz) {
before.push(mid);
mid = after.top(); after.pop();
} else {
after.push(mid);
mid = before.top(); before.pop();
}
befsiz = before.size(); aftsiz = after.size();
}
printf("%d\n", mid);
}
}
}
}

namespace Method2 {
/**
* 沙雕做法
* 使用 std::vector 和 std::lower_bound 手写堆
*/

std::vector<int> vec;

void _main() {
for (int i = 1; i <= n; ++i) {
int now = getint();
vec.insert(std::upper_bound(vec.begin(), vec.end(), now), now);
if (i & 1) printf("%d\n", vec.at(i / 2 + 1 - 1));
}
}
}

int main() {
n = getint();
if (1 + 1 == 3) Method2::_main();
else Method1::_main();
return 0;
}