A1029 Median (25 分)

一、技术总结

1. 最开始的想法是直接用一个vector容器，装下所有的元素，然后再使用sort()函数排序一下，再取出中值，岂不完美可是失败了，不知道是容器问题还是什么问题，就是编译没有报错，最后总是感觉不对，在PAT测试点也显示段错误。最后看别人的办法了。大部分是先判断出来中值的位置，然后存储两个数组，最后进行比较，当出现了小于median值的位置的时候那么就可以输出该数了。

二、参考代码

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 200010;
const int inf = 0x7fffffff;
int a[maxn], b[maxn];
int main(){
    int n1, n2;
    cin >> n1;
    for(int i = 0; i < n1; i++){
        scanf("%d", &a[i]);
    }
    cin >> n2;
    for(int i = 0; i < n2; i++){
        scanf("%d", &b[i]);
    }
    a[n1] = inf, b[n2] = inf;
    int median = (n1+n2-1)/2;
    int i = 0, j = 0, count = 0;
    while(count < median){
        if(a[i] < b[j]) i++;
        else j++;
        count++;
    }
    if(a[i] < b[j]) printf("%d", a[i]);
    else printf("%d", b[j]);
    return 0;
}