【洛谷】【堆】P1168 中位数
【题目描述：】
给出一个长度为N的非负整数序列A[i]，对于所有1 ≤ k ≤ (N + 1) / 2，输出A[1], A[3], …, A[2k - 1]的中位数。即前1，3，5，……个数的中位数。
【输入格式：】
输入文件median.in的第1行为一个正整数N，表示了序列长度。
第2行包含N个非负整数A[i] (A[i] ≤ 10^9)。
【输出格式：】
输出文件median.out包含(N + 1) / 2行，第i行为A[1], A[3], …, A[2i – 1]的中位数。
输入样例#1： 7 1 3 5 7 9 11 6 输出样例#1： 1 3 5 6输入输出样例
【算法分析：】
开一个大根堆一个小根堆，
小根堆里放大数，大根堆里放小数，保证两个堆的大小差值小于等于1
这样最后元素个数多的堆的堆顶就是中位数。
读入数列a，把a1 push进大根堆
对于a中的每一个数：
如果比大根堆的堆顶大就放进小根堆
否则放进大根堆
为了保证两个堆中的元素个数相差小于等于1：
不停地把元素多的堆的堆顶push到元素少的堆里去
最后元素多的堆的堆顶便是数列的中位数
【代码：】
1 //中位数 2 #include<iostream> 3 #include<cstdio> 4 #include<algorithm> 5 #include<queue> 6 #include<cmath> 7 using namespace std; 8 9 const int MAXN = 100000 + 1; 10 11 int n, a[MAXN]; 12 priority_queue<int> q1; 13 priority_queue<int, vector<int>, greater<int> > q2; 14 15 int main() { 16 scanf("%d", &n); 17 for(int i = 1; i <= n; i++) scanf("%d", &a[i]); 18 q1.push(a[1]); 19 printf("%d\n", a[1]); 20 for(int i = 2; i <= n; i++) { 21 if(a[i] > q1.top()) q2.push(a[i]); 22 else q1.push(a[i]); 23 while(abs(q1.size() - q2.size()) > 1) { 24 if(q1.size() > q2.size()) q2.push(q1.top()), q1.pop(); 25 else q1.push(q2.top()), q2.pop(); 26 } 27 if(i & 1) { 28 if(q1.size() > q2.size()) printf("%d\n", q1.top()); 29 else printf("%d\n", q2.top()); 30 } 31 } 32 }优质内容筛选与推荐>>
1、httpWebRequest请求错误,基础连接已经关闭: 连接被意外关闭
2、BeginPaint与GetDC获取设备环境的区别
3、Enterprise Library 4.1 一步一步从入门到精通（未完成）
4、C#面向对象设计模式学习笔记(10) - Facade 外观模式(结构型模式)
5、[数据模型] 数据表三种关联的概述