Description
题目描述非常简洁，不作解释。
Solution
题目要求对前奇数项求中位数？朴素的做法是暴力，但是范围1e5显然T。这里主要介绍一种堆顶堆的做法。
堆顶堆是什么呢？我们不妨开两个堆，一个大根堆一个小根堆。动态维护中位数，初始令前1位的中位数为\(a_i\)，遍历数组，若遇到比中位数\(m\)小的数则放到大根堆，否则放到小根堆。
我们发现，若大根堆内的元素数=小根堆内的元素数时，\(m\)恰好为此时的中位数。若不满足呢？分类讨论一下：
- 若大根堆内元素数 > 小根堆内元素数，则此时的中位数为大根堆堆顶，把原来的\(m\)放到小根堆。
- 反之则中位数肯定在小根堆，把原来的\(m\)放到大根堆，小根堆堆顶为\(m\)
我们发现，每次遍历到奇数时，进行上述操作使两个堆平衡，平衡完的\(m\)显然就是此时的中位数。
Code
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#define N 100010
using namespace std;
priority_queue <int> q1; //开大根堆和小根堆
priority_queue<int,vector<int>,greater<int> >q2;
int mid;
int n;
int a[N];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
mid = a[1];
cout<<mid<<endl;
for(int i=2;i<=n;i++)
{
if(a[i] > mid) q2.push(a[i]);
else q1.push(a[i]);
if(i%2 == 1)
{
while(q1.size() != q2.size()) //查询到奇数动态平衡
{
if(q1.size() > q2.size())
{
q2.push(mid);
mid = q1.top();
q1.pop();
}
else
{
q1.push(mid);
mid = q2.top();
q2.pop();
}
}
cout<<mid<<endl;
}
}
}