题目描述
给出一个长度为NN的非负整数序列A_iA i ? ，对于所有1 ≤ k ≤ (N + 1) / 21≤k≤(N+1)/2，输出A_1, A3, …, A{2k - 1}A 1 ? ,A 3 ? ,…,A 2k−1 ? 的中位数。即前1,3,5,…1,3,5,…个数的中位数。
输入输出格式
输入格式： 第11行为一个正整数NN，表示了序列长度。
第22行包含NN个非负整数A_i (A_i ≤ 10^9)A i ? (A i ? ≤10 9 )。
输出格式： 共(N + 1) / 2(N+1)/2行，第ii行为A_1, A3, …, A{2k - 1}A 1 ? ,A 3 ? ,…,A 2k−1 ? 的中位数。
输入输出样例
输入样例#1： 复制 7 1 3 5 7 9 11 6 输出样例#1： 复制 1 3 5 6 说明
对于20\%20%的数据，N ≤ 100N≤100；
对于40\%40%的数据，N ≤ 3000N≤3000；
对于100\%100%的数据，N ≤ 100000N≤100000。
题解：emmm一道二叉堆。第一次接触堆，好吃力嘤嘤嘤。一个大根堆，一个小根堆。大的存小数据，小的存大数据。
#include<cstdio> #include<iostream> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> #include<queue> typedef long long ll; using namespace std; priority_queue<int, vector<int>, greater<int> > q1;//小根堆,存较大数 priority_queue<int, vector<int>, less<int> > q2; //大根堆，存较小数 int n,x; void work(int x){ if(q1.empty()==1) q1.push(x); else if(x>q1.top()) q1.push(x); else q2.push(x); while(q1.size()<q2.size()){ q1.push(q2.top()); q2.pop(); } while(q1.size()>q2.size()){ q2.push(q1.top()); q1.pop(); } } int main(){ freopen("1168.in","r",stdin); freopen("1168.out","w",stdout); cin>>n; for(int i=1;i<=n;i++){ cin>>x; work(x); if(i%2==1) cout<<q1.top()<<endl; } //cout<<ans; return 0; }
原文：https://www.cnblogs.com/wuhu-JJJ/p/11149946.html