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);
if(maxHeap.size() > minHeap.size() + 1)
{
int t_max = maxHeap.top();
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";
}
}
}
}