PAT-A 1029. Median

Given an increasing sequence S of N integers, the median is the number at the middle position. For example, the median of S1={11, 12, 13, 14} is 12, and the median of S2={9, 10, 15, 16, 17} is 15. The median of two sequences is defined to be the median of the nondecreasing sequence which contains all the elements of both sequences. For example, the median of S1 and S2 is 13.

Given two increasing sequences of integers, you are asked to find their median.

Input

Each input file contains one test case. Each case occupies 2 lines, each gives the information of a sequence. For each sequence, the first positive integer N (<=1000000) is the size of that sequence. Then N integers follow, separated by a space. It is guaranteed that all the integers are in the range of long int.

Output

For each test case you should output the median of the two given sequences in a line.

Sample Input

4 11 12 13 14
5 9 10 15 16 17

Sample Output

13

程序代码:

#include<stdio.h>
#define MAX 1000000
long a[MAX];
long b[MAX];
int main()
{
    long long m,n,i;
    scanf("%lld",&m);
    for(i=0;i<m;i++)
        scanf("%lld",&a[i]);
    scanf("%lld",&n);
    for(i=0;i<n;i++)
        scanf("%lld",&b[i]);
    long long sum = (m+n+1)/2,count = 0;
    long *p=&a[0],*q=&b[0],*s;
    while(p<=&a[m-1]&&q<=&b[n-1])
    {
        if(*p<*q)
        {
            count++;
            s=p;
            p++;
        }
        else
        {
            count++;
            s=q;
            q++;
        }
        if(count==sum)
        {
            printf("%ld",*s);
            return 0;
        }

    }
    if(count<sum)
    {
        while(p<=&a[m-1])
        {
            count++;
            s=p;
            p++;
            if(count == sum)
            {
                printf("%ld",*s);
                return 0;
            }
        }
        while(q<=&b[n-1])
        {
            count++;
            s=q;
            q++;    
            if(count==sum)
            {
                printf("%ld",*s);
                return 0;
            }
        }
    }
    return 1;
}
全部评论

相关推荐

本人一直追求WLB,对大小周深恶痛疾,刷到小红书说取消大小周大喜,看来跳槽的选择又多一个了
一枚大铁锤:至于冲不冲小红书,这是个问题,我先声明我不是这方面的专家,我觉得这件事还是要慎重评论,你问我为什么不给出回答,因为我一开始就说了,我不是这方面的专家
点赞 评论 收藏
分享
永不遗忘:才这么点算什么拉黑,我初筛连着挂几十次了,最后还是能进面
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务