P1168 中位数

目录

题目描述

输入格式

输出格式

输入输出样例

说明/提示

代码

无注释版

有注释版

---

题目描述

给定一个长度为 N 的非负整数序列 A，对于前奇数项求中位数。

输入格式

第一行一个正整数 N。

第二行 N 个正整数 A1…N​。

输出格式

共 ⌊2N+1​⌋ 行，第 i 行为 A1…2i−1​ 的中位数。

输入输出样例

输入 

7
1 3 5 7 9 11 6

输出 

1
3
5
6

输入 

7
3 1 5 9 8 7 6

输出 

3
3
5
6

说明/提示

对于 20% 的数据，N≤100；

对于 40% 的数据，N≤3000；

对于 100% 的数据，1≤N≤100000，0≤Ai​≤109。

代码

无注释版

#include<bits/stdc++.h>
using namespace std;
priority_queue<int> L;
priority_queue<int,vector<int>,greater<int> > R; 
int main(){int n,M;cin>>n>>M;cout<<M<<"\n";int m=(n-1)/2;while(m--){int a,b;cin>>a>>b;if(a>b) swap(a,b);if(M>=a&&M<=b){R.push(b);L.push(a);}else if(M<a){L.push(M);R.push(a);R.push(b);M=R.top();R.pop();}else{R.push(M);L.push(a);L.push(b);M=L.top();L.pop();}cout<<M<<"\n";}
}

有注释版

#include<bits/stdc++.h> // 引入所有标准库
using namespace std;// 定义两个堆
priority_queue<int> L; // 大顶堆，存较小的一半（左边）
priority_queue<int,vector<int>,greater<int>> R; // 小顶堆，存较大的一半（右边）int main(){int n, M;cin >> n >> M; // 输入序列长度 n，输入第一个数 Mcout << M << "\n"; // 第一个数本身就是第一个中位数，直接输出int m = (n-1)/2; // 需要输出的剩余中位数的数量（每次读两个数，m 次）while(m--){ // 每次处理两个新读入的数int a, b;cin >> a >> b; // 读入两个数if(a > b) swap(a, b); // 保证 a <= b，方便后续处理if(M >= a && M <= b){// 当前中位数 M 在 [a, b] 之间// M 继续作为新的中位数R.push(b); // 把 b 放入右边小顶堆L.push(a); // 把 a 放入左边大顶堆}else if(M < a){// 当前 M 比 a 小，说明 a、b 都比 M 大L.push(M); // M 插入左堆R.push(a); // a 插入右堆R.push(b); // b 插入右堆M = R.top(); // 取右堆最小的元素作为新的中位数R.pop();     // 从右堆弹出新的中位数}else{// 当前 M 比 b 大，说明 a、b 都比 M 小R.push(M); // M 插入右堆L.push(a); // a 插入左堆L.push(b); // b 插入左堆M = L.top(); // 取左堆最大的元素作为新的中位数L.pop();     // 从左堆弹出新的中位数}cout << M << "\n"; // 输出当前的中位数}
}