题目
题意分析:
这道题目题意其实并不理解,相当于在插入数据的过程中动态求中位数,每当插入奇数个数据时就求这所有奇数个数据的中位数。
做题思路:
代码实现
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,a[200000],mid;
cin>>n;
//利用优先队列实现堆的结构
priority_queue<int,vector<int>,less<int> > lar; //建立一个大根堆
priority_queue<int,vector<int>,greater<int> > sma; //建立一个小根堆
cin>>a[1];
mid=a[1]; //开始时mid时第一个数据元素
cout<<a[1]<<endl;
for(int i=2;i<=n;i++)
{
cin>>a[i];
if(a[i]>mid)
{
sma.push(a[i]);
}
else
{
lar.push(a[i]);
}
if(i&1) //看网上的代码看到一位大神这样写的,其实相当于判断i是否是奇数
{
while(sma.size()!=lar.size()) //当两个堆的元素个数不相等时
{
if(sma.size()>lar.size())
{
lar.push(mid);
mid=sma.top();
sma.pop();
}
else
{
sma.push(mid);
mid=lar.top();
lar.pop();
}
}
cout<<mid<<endl;
}
}
return 0;
}
```**加粗样式**