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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
#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("%d\n",v[i/2]); } return 0; } |
