Running Median 优先队列

Running Median

对顶堆写法
题目描述
Running Median题解

思路：
大根堆维护当前序列中较小的一半元素。

大根堆中的数据为当前序列中最小段那部分。因为序列是大根堆，所以堆顶为当前序列中最大的数。

小根堆维护较大的一半元素。

小根堆中的数据为当前序列中最大段那部分。同理，所以堆顶为当前序列中最小的数。

注意细节，如果两个堆的大小差距超过1的话，就要把另一个数量多的堆顶给另外一个数量少的堆。记得堆顶弹出

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define INF 0x3f3f3f3f
#define PII pair<int, int>
#define rep(i, l, r) for (int i = l; i < r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define rep2(i, l, r) for (int i = l; i * i <= r; i++)
#define rep3(i, l, r) for (LL i = l; i * i * i <= r; i++)
#define Min(a, b) a > b ? b : a
#define Max(a, b) a > b ? a : b
#define endl 'n'
#define debug "-----"
using namespace std;
typedef long long LL;
const LL mod = 1e9;
const int N = 1e6 + 10, M = 10100;
LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; }
int p,m,k;
int ans[N];
int main()
{
IOS;
int t;
cin >> t;
while(t--){
k = 0;
cin >> p >> m;
cout << p << ' ' << (m+1)/2 << endl;
//大根堆维护当前序列中较小的一半元素
//小根堆维护较大的一半元素
priority_queue<int,vector<int>,greater<int>>q1;
priority_queue<int>q2;
int x; cin >> x;
q1.push( x );
cout << x << ' ';
rep( i , 2 , m+1 ){
int a; cin >> a;
if( q1.top() >= a ) q2.push( a );
else q1.push( a );
if (q1.size() > q2.size() + 1)
{
q2.push(q1.top());
q1.pop();
}
else if (q1.size() + 1 < q2.size())
{
q1.push(q2.top());
q2.pop();
}
if( i&1 ){
if( q1.size() > q2.size() ) cout << q1.top() << ' ';
else cout << q2.top() << ' ';
}
if( i%20 == 0 ) cout << endl;
}
cout << endl;
}
return 0;
}

最后

以上就是怕黑麦片为你收集整理的Running Median 优先队列的全部内容，希望文章能够帮你解决Running Median 优先队列所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。