原题链接:https://www.luogu.com.cn/problem/P1168
题意解读:中位数就是位于中间的数,前1个数的中位数是第1个,前3个数的中位数是第2个,前5个数的中位数的第3个...以此类推。
所以,此题本质上就是动态维护一组数,每1/3/5...等奇数个取第k小的数,取一次后k++。
解题思路:
要动态维护数据,且每次取第k小的数,又有多种做法:快选、平衡树、双堆,这里依然采用双堆做法:
定义一个小根堆,一个大根堆,确保小根堆的堆顶大于大根堆的堆顶,大根堆的元素个数保持在k-1个,这样每次取小根堆的堆顶即是第k小的数。
本题和P1801 黑匣子本质上是一样的。
100分代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int n, a;
priority_queue<int> q1; //大根堆
priority_queue<int, vector<int>, greater<int>> q2; //小根堆
int cnt;
int main()
{
cin >> n;
for(int i = 1; i <= n; i++)
{
cin >> a;
q1.push(a);
if(q1.size() > cnt) //如果大根堆超过cnt个
{
q2.push(q1.top()); //将大根堆堆顶移至小根堆
q1.pop();
}
if(i % 2 == 1) //每奇数个
{
cout << q2.top() << endl; //输出第cnt+1小的值
cnt++; //cnt下次+1
if(q1.size() < cnt) //如果大根堆不足cnt个
{
q1.push(q2.top()); //将小根堆堆顶移至大根堆
q2.pop();
}
}
}
return 0;
}
标签:q1,大根堆,cnt,int,洛谷题,中位数,二叉,小根堆,P1168 From: https://www.cnblogs.com/jcwy/p/18534554