今天做https://www.luogu.com.cn/problem/P1168

中位数

题目描述

给定一个长度为 $N$ 的非负整数序列 $A$ ，对于前奇数项求中位数。

输入格式

第一行一个正整数 $N$ 。第二行 $N$ 个正整数 $A_{1\dots N}$ 。

输出格式

共 $\lfloor \frac{N + 1}2\rfloor$ 行，第 $i$ 行为 $A_{1\dots 2i - 1}$ 的中位数。

样例 #1

样例输入 #1


7
1 3 5 7 9 11 6

样例输出 #1

样例 #2

样例输入 #2


7
3 1 5 9 8 7 6

样例输出 #2

提示

对于 $20\%$ 的数据， $N \le 100$ ；对于 $40\%$ 的数据， $N \le 3000$ ；对于 $100\%$ 的数据， $1 \le N ≤ 100000$ ， $0 \le A_i \le 10^9$ 。

用到的对顶堆算法

对顶堆算法（Median Maintenance Algorithm）是一种用于动态维护中位数的算法。它的核心思想是使用两个堆来分别存储数据集的较小一半和较大一半的元素，从而能够快速找到中位数。

核心思想：

两个堆：
- 大顶堆（max heap）：存储较小的一半元素。
- 小顶堆（min heap）：存储较大的一半元素。
平衡条件：
- 大顶堆的堆顶元素是较小一半的最大值。
- 小顶堆的堆顶元素是较大一半的最小值。
- 两个堆的大小差不能超过1。
中位数：
- 如果两个堆的大小相等，中位数是两个堆顶元素的平均值。
- 如果两个堆的大小不相等，中位数是较大堆的堆顶元素。

具体步骤：

初始化两个堆：
- max_heap：大顶堆，存储较小的一半元素。
- min_heap：小顶堆，存储较大的一半元素。
遍历序列：
- 对于每个元素，先将其插入到大顶堆中。
- 检查大顶堆和小顶堆的大小关系：
  - 如果大顶堆的元素数量比小顶堆的元素数量多出2个或更多，则将大顶堆的堆顶元素移到小顶堆中。
  - 如果大顶堆的堆顶元素大于小顶堆的堆顶元素，则交换这两个堆的堆顶元素。
输出中位数：
- 每次处理完奇数个元素后，大顶堆的堆顶元素就是当前序列的中位数。

具体例子：

假设输入序列为 [3, 1, 5, 9, 8, 7, 6]，我们逐步分析：

插入第一个元素 3：
- max_heap：[3]
- min_heap：空
- 中位数：3
- 输出：3
插入第二个元素 1：
- max_heap：[3, 1]
- min_heap：空
- 调整：max_heap 的元素数量比 min_heap 多出2个，将 3 移到 min_heap
- max_heap：[1]
- min_heap：[3]
- 中位数：3
- 输出：3
插入第三个元素 5：
- max_heap：[5, 1]
- min_heap：[3]
- 调整：max_heap 的堆顶元素 5 大于 min_heap 的堆顶元素 3，交换
- max_heap：[3, 1]
- min_heap：[5]
- 中位数：3
- 输出：3
插入第四个元素 9：
- max_heap：[9, 3, 1]
- min_heap：[5]
- 调整：max_heap 的元素数量比 min_heap 多出2个，将 9 移到 min_heap
- max_heap：[3, 1]
- min_heap：[5, 9]
- 中位数：5
- 输出：5
插入第五个元素 8：
- max_heap：[8, 3, 1]
- min_heap：[5, 9]
- 调整：max_heap 的堆顶元素 8 大于 min_heap 的堆顶元素 5，交换
- max_heap：[5, 3, 1]
- min_heap：[8, 9]
- 中位数：5
- 输出：5
插入第六个元素 7：
- max_heap：[7, 5, 3, 1]
- min_heap：[8, 9]
- 调整：max_heap 的元素数量比 min_heap 多出2个，将 7 移到 min_heap
- max_heap：[5, 3, 1]
- min_heap：[7, 8, 9]
- 中位数：6
- 输出：6
插入第七个元素 6：
- max_heap：[6, 5, 3, 1]
- min_heap：[7, 8, 9]
- 调整：max_heap 的堆顶元素 6 大于 min_heap 的堆顶元素 7，交换
- max_heap：[5, 3, 1]
- min_heap：[6, 7, 8, 9]
- 中位数：6
- 输出：6

复杂度分析：

时间复杂度：每次插入和调整堆的时间复杂度为 (O(\log k))，其中 (k) 是当前堆的大小。总的时间复杂度为 (O(N \log N))。
空间复杂度：两个堆的空间复杂度为 (O(N))。

代码实现：

cpp
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
void find_medians(int N, vector<int>& A) {
    priority_queue<int> max_heap;  // 大顶堆，存储较小的一半元素
    priority_queue<int, vector<int>, greater<int>> min_heap;  // 小顶堆，存储较大的一半元素
    
    for (int i = 0; i < N; ++i) {
        // 将当前元素插入到大顶堆中
        max_heap.push(A[i]);
        
        // 如果大顶堆的元素数量比小顶堆的元素数量多出2个或更多
        if (max_heap.size() > min_heap.size() + 1) {
            // 将大顶堆的堆顶元素移到小顶堆中
            min_heap.push(max_heap.top());
            max_heap.pop();
        }
        
        // 如果大顶堆的堆顶元素大于小顶堆的堆顶元素
        if (!min_heap.empty() && max_heap.top() > min_heap.top()) {
            // 交换这两个堆的堆顶元素
            int max_top = max_heap.top();
            int min_top = min_heap.top();
            max_heap.pop();
            min_heap.pop();
            max_heap.push(min_top);
            min_heap.push(max_top);
        }
        
        // 如果当前处理的是奇数个元素
        if ((i + 1) % 2 == 1) {
            // 输出大顶堆的堆顶元素，即当前序列的中位数
            cout << max_heap.top() << endl;
        }
    }
}
int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }
    
    find_medians(N, A);
    
    return 0;
}

巧妙的利用了大小堆的性质

目录

中位数