首页 > 其他 > 详细

洛谷P1168 中位数 题解 堆/优先队列

时间:2020-02-16 19:52:03      阅读:78      评论:0      收藏:0      [点我收藏+]

题目链接:https://www.luogu.com.cn/problem/P1168

解题思路:
开一个大根堆维护前 \(\lfloor \frac{i}{2} \rfloor\) 个较小的元素;
开一个小根堆维护前 \(\lceil \frac{i}{2} \rceil\) 个较大的元素。

然后每次碰到奇数 \(i\) ,中位数即为小根堆的堆顶元素。

这里使用优先队列(priority_queue)来模拟堆。

实现代码如下:

#include <bits/stdc++.h>
using namespace std;
int n, a;
priority_queue<int> big_heap;
priority_queue<int, vector<int>, greater<int> > small_heap;
int main() {
    cin >> n;
    for (int i = 1; i <= n; i ++) {
        cin >> a;
        if (i==1 || a <= big_heap.top()) big_heap.push(a);
        else small_heap.push(a);
        if (big_heap.size() > i/2) {
            small_heap.push(big_heap.top());
            big_heap.pop();
        }
        if (small_heap.size() > (i+1)/2) {
            big_heap.push(small_heap.top());
            small_heap.pop();
        }
        if (i % 2)
            cout << small_heap.top() << endl;
    }
    return 0;
}

洛谷P1168 中位数 题解 堆/优先队列

原文:https://www.cnblogs.com/quanjun/p/12317957.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!