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;
}
上一篇:【PAT甲级】1029 Median (25 分)


下一篇:Codeforces Round #644 (Div. 3) H. Binary Median