当前位置：首页 > 洛谷 > 洛谷P1168题：中位数解题思路全解析，C++实现

洛谷P1168题：中位数解题思路全解析，C++实现

12小时前

一、题目解读

洛谷P1168题要求处理一个动态数据流，实时输出前奇数项的中位数。中位数定义为有序数列中间位置的元素，需解决数据插入与统计的实时性。题目核心在于设计高效数据结构，快速定位中位数并应对数据变化。

二、解题思路

采用“双堆平衡”策略：

1. 使用大根堆（max_heap）存储较小的一半数，小根堆（min_heap）存储较大的一半数。

2. 通过动态调整两堆元素数量（差值为0或1），确保中位数始终位于max_heap的堆顶。

3. 新元素根据大小分配至对应堆，并利用堆自动排序特性，避免手动排序开销。

此思路将插入与维护复杂度控制在O(logn)，总时间复杂度为O(nlogn)。

三、解题步骤

1. 输入处理：读取N个数存入数组A，关闭流同步提升效率。

2. 初始化堆：创建大根堆max_heap和小根堆min_heap（需指定比较器）。

3. 循环插入与平衡：

若max_heap为空或新元素≤max_heap.top，插入max_heap；否则插入min_heap。

若两堆数量差超过1，通过交换堆顶元素恢复平衡（大数移入min_heap，小数移入max_heap）。

4. 输出中位数：奇数项时输出max_heap.top()，偶数项无需输出。

四、代码与注释

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
    ios::sync_with_stdio(false); // 关闭流同步加速输入
    cin.tie(nullptr);
    
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }
    
    // 大根堆存储较小的一半数
    priority_queue<int> max_heap;
    // 小根堆存储较大的一半数
    priority_queue<int, vector<int>, greater<int>> min_heap;
    
    for (int i = 0; i < N; ++i) {
        // 将新元素插入到合适的堆中
        if (max_heap.empty() || A[i] <= max_heap.top()) {
            max_heap.push(A[i]);
        } else {
            min_heap.push(A[i]);
        }
        
        // 平衡两个堆的大小，保持max_heap比min_heap多0或1个元素
        if (max_heap.size() > min_heap.size() + 1) {
            min_heap.push(max_heap.top());
            max_heap.pop();
        } else if (min_heap.size() > max_heap.size()) {
            max_heap.push(min_heap.top());
            min_heap.pop();
        }
        
        // 输出前奇数项的中位数
        if ((i + 1) % 2 == 1) {
            cout << max_heap.top() << "\n";
        }
    }
    
    return 0;
}

注释说明：

使用priority_queue分别构建大根堆（默认）和小根堆（通过greater<int>指定比较器）。

平衡操作通过堆顶交换维持两堆元素差，保证中位数在max_heap中。

奇数项输出优化减少冗余计算。