AcWing 106. 动态中位数
原题链接
中等
作者:
烟花易冷
,
2020-08-17 20:53:23
,
所有人可见
,
阅读 461
拿54题改改就行了。。。
#include <bits/stdc++.h>
using namespace std;
int t, x, n, now, cnt;
priority_queue<int> maxHeap;//优先队列声明大顶堆
priority_queue<int, vector<int>, greater<int>> minHeap;//优先队列声明小顶堆
void insert(int num)
{
maxHeap.push(num);//推n入大顶堆
if(maxHeap.size() > minHeap.size() + 1)//大顶堆比小顶堆+1大
{
int t_max = maxHeap.top();//t_max=最大值
maxHeap.pop();//删除最大值
minHeap.push(t_max);//推入小顶堆
}
while(minHeap.size() && maxHeap.top() > minHeap.top())//大顶堆最大值 比 小顶堆最小值大 且 小顶堆存在
{
int t1 = maxHeap.top();//交换两个极值
int t2 = minHeap.top();
maxHeap.pop(); maxHeap.push(t2);
minHeap.pop(); minHeap.push(t1);
}
}
int main()
{
cin >> t;
while(t --)
{
cnt = 0;
while (!maxHeap.empty()) maxHeap.pop();
while (!minHeap.empty()) minHeap.pop();
cin >> x >> n;// 编号&输入数据个数
cout << x << " " << (n + 1) / 2 << endl;// 输出编号及中位数个数
for (int i = 1; i <= n; i ++)
{
cin >> now;
insert(now);
if (i & 1)// 输出奇数项
{
cnt ++;
cout << maxHeap.top();
if(cnt != (n + 1) / 2)
cout << " ";
if (!(cnt % 10) || cnt == (n + 1) / 2)// 满十个或最后一个,要换行
cout << "\n";
}
}
}
}