中位数
前言：
被教练当作数据结构和STL的阶段性测试题，考试时候觉得sort会爆超多（打脸啊，sort可是40ptsQAQ）就没写
然后顺利的敲了个暴力，20pts滚粗（不过我好像也就编了几分钟...）
当时的思路就是开两层循环，用一个小根堆来做，暴力嘛，能骗多少骗多少
题目简述：
给你长度为n的序列Ai，（n≤10^5,Ai≤10^9）
要求输出奇数个数的中位数（即输出前1、3、5、7···个数的中位数）
解题思路：
- STL：vector+lower_bound函数
（这大概是这题最短的代码了吧？）
因为每次插入后再排序肯定会超时的，所以我们在插入前就进行排序（并不是每次从头排序哦！）
解决了排序，就能让之前在vector中的元素保持单调性，那我们怎么知道当前的元素x该插入什么位置呢？
如果你对STL函数库足够熟悉的话，那么就能想到，STL中有现成的函数可以帮助我们实现这个期望：lower_bound函数
scanf("%d",&x);
a.insert(lower_bound(a.begin(),a.end(),x),x); //lower_bound返回的是在[a.begin(),a.end())这个区间内第一个大于等于x的元素的迭代器
这里的a是一个vector<int>类型的
补充一下：insert(it,x)用来向vector的任意迭代器it处插入一个元素想，时间复杂度为O(N)
完整代码就不用放了吧？就是边输入边插入，遇到奇数个元素就输出中位数即可
- STL：大根堆&小根堆
（这个应该算是解决这道题最常见的思路了）
要维护中位数，那我们整两个堆，一个大根堆存放小于等于中位数的数，一个小根堆存放大于中位数的数
很显然，小根堆的堆顶是第一个大于mid的数，大根堆堆顶是第一个小于等于mid的数字（我们设mid为中位数，mid初始就是第一个元素）
scanf("%d",&mid); //第一个数直接输入mid即可
printf("%d
",mid); //第一个也直接输出
每一次输入一个元素x，我们就判断该放入哪个堆：
scanf("%d",&x);
if(x>mid) shans.push(x); //大于中间值，进入小根堆
else shan.push(x); //否则进入大根堆
如果遇到奇数个元素，我们就先维护两个堆的元素个数相同（因为只有两个堆的元素个数相同，那mid才能是中位数）
维护元素个数很简单：如果大根堆多于小根堆，就把当前mid存入小根堆，将大根堆对顶赋给mid再删除堆顶，直到元素个数相同（小根堆多的话反过来就是了）
if(i%2==1) { //奇数个数就输出
while(shan.size()!=shans.size()) { //维护两个堆的元素个数相等，保证mid始终是中位数
if(shan.size()>shans.size()) {
shans.push(mid);
mid=shan.top();
shan.pop();
}
else {
shan.push(mid);
mid=shans.top();
shans.pop();
}
}
printf("%d
",mid);
}
完整Code：
如下是第二种思路的代码
#include <bits/stdc++.h>
using namespace std;
int n,x,mid;
priority_queue<int,vector<int>,less<int> > shan; //大根堆存小于等于mid的数
priority_queue<int,vector<int>,greater<int> > shans; //小根堆存大于mid的数
//小根堆的堆顶是第一个大于mid的数，大根堆堆顶是第一个小于等于mid的数字
int main() {
scanf("%d",&n);
scanf("%d",&mid); //第一个数直接输入mid即可
printf("%d
",mid);
for(register int i=2;i<=n;i++) {
scanf("%d",&x);
if(x>mid) shans.push(x); //大于中间值，进入小根堆
else shan.push(x); //否则进入大根堆
if(i%2==1) { //奇数个数就输出
while(shan.size()!=shans.size()) { //维护两个堆的元素个数相等，保证mid始终是中位数
if(shan.size()>shans.size()) {
shans.push(mid);
mid=shan.top();
shan.pop();
}
else {
shan.push(mid);
mid=shans.top();
shans.pop();
}
}
printf("%d
",mid);
}
}
return 0;
}
后序：
还能用平衡树做，但我不配啊（太菜）
所以在这里只是提一下这种做法，大家可以去看看其他dalao的博客
最后：第一种超短代码的思路来自：deco大佬的题解 感谢orz