Luogu P1168 中位数 题解
Description
题目链接
给出一个长度为 N 的非负整数序列 A_i，对于所有 1 ≤ k ≤ (N 1) / 2，输出 A_1, A_1 sim A_3, …,A_1 sim A_{2k - 1} 的中位数。即前 1,3,5,… 个数的中位数。
Solution
众所周知，vector 可以当平衡树来用。
Code
代码语言：javascript复制#include<cstdio>
#include<vector>
const int N=100010;
int n,a[N];
std::vector<int> v;
int main(){
scanf("%d",&n);for(int i=1;i<=n;i ) scanf("%d",&a[i]);
for(int i=1;i<=n;i ){
v.insert(lower_bound(v.begin(),v.end(),a[i]),a[i]);
if(i&1) printf("%dn",v[i/2]);
}
return 0;
}
