洛谷P1168《中位数》

十月 02, 2019 3523

两个优先队列

解析

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

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

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

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

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

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

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

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

本方法对应代码中的 Method1

或者可以直接使用 std::vector 和 std::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
95
//
//  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;
}