水题笔记_ poj3784 Running Median [对顶堆, 清奇脑回路]

颓废是人类进步的阶梯

懵逼的 题目

传送至 破甲

扯淡的 题解

po大爷blog的时候发现了这个玩意…感觉非常资瓷啊qwqwqwqwqwq

对顶堆

就是维护一个小根堆和一个大根堆, 小根堆的所有数都大于大根堆里的所有数, 插入一个数$x$就把$x$与当前的中位数比较
$$
\begin{cases}
maxq.push(x)\,\,\,\,x \le mid \\
minq.push(x)\,\,\,\,x > mid
\end{cases}
$$
然后平衡两个堆的大小, 怎么平衡? 直接暴力平衡! 每次平衡都是$\mathrm O(1)$的怂什么!

然后$size$较大的堆的堆顶就是中位数了qwq

沙茶的 代码

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define MAXN (10000 + 5)
using namespace std;
int n, ans[MAXN];
struct cmp1
{
bool operator () (const int x, const int y)
{ return x < y; }
};
struct cmp2
{
bool operator () (const int x, const int y)
{ return x > y; }
};
int main()
{
// cout << "Hello world!" << endl;
freopen("in.in", "r", stdin);
int t;
scanf("%d", &t);
while (t--)
{
int n;
scanf("%d%d", &ans[0], &n);
priority_queue<int, vector<int>, cmp1> maxq;
priority_queue<int, vector<int>, cmp2> minq;
int srx;
scanf("%d", &srx);
minq.push(srx);
ans[1] = srx;
for (int i = 2; i <= n; i++)
{
scanf("%d", &srx);
if (srx < ans[i >> 1]) maxq.push(srx);
else minq.push(srx);
while (maxq.size() > minq.size() + 1)
minq.push(maxq.top()), maxq.pop();
while (minq.size() > maxq.size() + 1)
maxq.push(minq.top()), minq.pop();
if (i & 1)
ans[(i + 1) >> 1] = ((maxq.size() > minq.size()) ? maxq.top() : minq.top());
}
printf("%d %d\n", ans[0], (n + 1) >> 1);
for (int i = 1; i <= ((n + 1) >> 1); i++)
printf("%d%c", ans[i], (i % 10 == 0 ? '\n' : ' '));
if (((n + 1) >> 1) % 10)
puts("");
}
return 0;
}

/*
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
*/

By 可能是闲得蛋疼的 Cansult