1029 Median (25分)

题目大意:将两个数列合并成一个数列后,若数列长度为奇数,则求其中位数,若数列长度为偶数,求中间两数中的前者。

思路:以为是个王者,没想到是个青铜。合成后的数列长度最大为4e5,因此直接sort就行。最终结果为(len-1)/2,此处len为合成后的数列长度,下标从0开始储存。
如果数列长度能够达到1e7的话,根据题意,两个数列均为升序,那么应该借助归并排序的思想来实现

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N=4e5+5;

int a[N];

int main()
{
    int n1,n2;
    scanf("%d",&n1);
    for(int i=0;i<n1;i++)
        scanf("%d",&a[i]);
    scanf("%d",&n2);
    for(int i=0;i<n2;i++)
        scanf("%d",&a[i+n1]);

    sort(a,a+n1+n2);

    printf("%d\n",a[(n1+n2-1)/2]);

    return 0;
}

上一篇:SpringCloud(7)服务链路追踪Spring Cloud Sleuth


下一篇:寒假刷C语言题库的心得(大一)