1029 Median （25 分)

直接暴力排序，内存超限:

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
	int n,m,temp;
	scanf("%d", &n);
	vector<int> v;
	for (int i = 0; i < n; i++) {
		scanf("%d", &temp);
		v.push_back(temp);
	}
	scanf("%d", &m);
	for (int i = 0; i < m; i++) {
		scanf("%d", &temp);
		v.push_back(temp);
	}
	sort(v.begin(), v.end());
	printf("%d", v[(m + n - 1) / 2]);
	return 0;
}

说明不可以建两个字符串，会超内存。只能输入一行，另一行不存储，直接处理。参考他人代码，修改后的AC代码。

#include <stdio.h>
#include <vector>
using std::vector;
vector<int> v;

int main() {
	int n,m,temp;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &temp);
		v.push_back(temp);
	}
	v.push_back(0x7FFFFFFF); //假设比较过程中超出v的范围
	scanf("%d", &m);
	int mid = (m + n + 1) / 2, cnt = 0, k = 0;
	//mid为比较的次数
	for (int i = 0; i < m; i++) {
		scanf("%d", &temp);
		while (v[k]<temp){
			cnt++;
			if (cnt == mid) printf("%d", v[k]);
			k++;
		}
		cnt++;
		if (cnt == mid) printf("%d", temp);
	}
	while (k<n){
		cnt++;
		if (cnt == mid) printf("%d", v[k]);
		k++;
	}
	return 0;
}