洛谷p1168中位数题解
题目描述
给定一个长度为 N 的非负整数序列 A，对于前奇数项求中位数。
输入格式
第一行一个正整数 N。
第二行 N 个正整数 A1…N。
输出格式
共 ⌊(N+1)/2⌋ 行，第 i 行为 A1…2i−1的中位数。
输入输出样例
输入 #1复制
7 1 3 5 7 9 11 6
输出 #1复制
1 3 5 6
输入 #2复制
7 3 1 5 9 8 7 6
输出 #2复制
3 3 5 6
说明/提示
对于 20% 的数据，N≤100；
对于 40% 的数据，N≤3000；
对于 100% 的数据，1≤N≤100000，0≤Ai≤10^9。
思路:
STL裸题。
考虑每一次求中位数先排序，再求解，复杂度过高，会TLE，考虑每一次输入就将数据插入合适的位置，如果这是第奇数个数据那么输出当前的中位数。
考虑用vector和upper_bound。
Code：
#include<bits/stdc++.h>
using namespace std;
long long n,m;
vector<int> a;
int main(){cin>>n;for(int i=1;i<=n;i++){cin>>m;a.insert(upper_bound(a.begin(),a.end(),m),m);if(i&1)cout<<a[i/2]<<"\n";}
}