Running Median 对顶堆

题意：

给定一个数列，每次已经输入了奇数个数字的话，输出此时的中位数

思路:

对顶堆板子题

想象两个堆为一个三角形和一个倒三角形，组成的沙漏形状，即为对顶堆，两个堆相接之处则为答案

维护一个大根堆一个小根堆，保持这两个堆均分数组数据。询问时输出对顶即可

代码:

注意输出格式

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
priority_queue<int>down;
priority_queue<int, vector<int>, greater<int>>up;//小根堆
void init() {
while (down.size())
{
down.pop();
}
while (up.size())
{
up.pop();
}
return;
}
void slv() {
init();
int n, m;
cin >> n >> m;
cout << n << (m + 1) / 2 << endl;
int cnt = 0;
int t;
for (int i = 1; i <= m; i++) {
cin >> t;
if (up.empty()) {
up.push(t);
}
else if (t >= up.top()) {
up.push(t);
}
else {
down.push(t);
}
if (up.size() > down.size() + 1) {
down.push(up.top());
up.pop();
}
if (up.size() < down.size()) {
up.push(down.top());
down.pop();
}
if (i & 1) {
cout << up.top();
cnt++;
if (cnt != 10) {
cout << " ";
}
else {
cout << "n";
cnt = 0;
}
}
}
if (cnt) {
cout << "n";
}
}
int main(void) {
int t;
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
cin >> t;
while (t--)
{
slv();
}
return 0;
}

最后

以上就是能干睫毛为你收集整理的Running Median 对顶堆Running Median 对顶堆的全部内容，希望文章能够帮你解决Running Median 对顶堆Running Median 对顶堆所遇到的程序开发问题。

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