中位数

• 题目

• 题解

1. 首先我们可以想到，既然需要输出（n+1）/2次，所以我们可以每次排序一下，并在其为奇数的时候输出它们中间的数。

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
int N;
int a[100001];
int main() {	
	cin >> N;	
	for (int i = 0; i <N; i++) {
		cin >> a[i];
		sort(a, a + i+1 );
		if (i % 2 == 0) {
			cout << a[i/2] << endl;
		}
	}	
}

但这样肯定会超时因为每次都要排序一下。

2.那么就需要进行优化，可以想到如果能够直接插入到相应的位置就好了。

这样就很容易想到用stl容器的vector，insert（）刚好有插入的功能

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int N;
int a;
vector<int>v;
int main() {	
	cin >> N;	
	cin >> a;
	v.push_back(a);
	cout << v[0] << endl;
	for (int i = 1; i <N; i++) {
		cin >> a;	
		int s = 0;
		for (int j = 0; j < v.size(); j++) {
			if (a > v[j])
				s = j+1;
		}
		v.insert(v.begin() + s, a);
		if (i % 2 == 0) {
			cout << v[i/2] << endl;
		}
	}	
}

但是这里仍然使用for循环，大大增加了时间复杂度。

3.所以，需要把这里的循环也优化掉，那么很自然的想到了二分。

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int N;
int a;
vector<int>v;
int main() {	
	cin >> N;	
	for (int i = 0; i <N; i++) {
		cin >> a;	
		v.insert(lower_bound(v.begin(), v.end(), a), a);
		if (i % 2 == 0) {
			cout << v[i/2] << endl;
		}
	}	
}

这样就好啦！