PAT甲级1029.

目录

A1029

题目

样例

样例1

输入:

4 11 12 13 14
5 9 10 15 16 17

输出:

13

补充样例

输入:

1 1
1 2

输出:

1

思路和坑点

　　考虑到数据量比较大，而且直接合并排序的时间比较长，因此单独对每一个进行排序。然后，计算出中位数是第k个，每次从两个序列中弹出一个小的数，直到弹出了k-1个之后，下一个要被弹出的便是中位数。可以使用一个标记来标识在k-1之后只进行一次便推出循环，省去了最后找第k个的的代码重复。
　　坑点
　　对于每个序列只有一个的情况，需要特判一下，不然我这个循环会因为这种情况陷入死循环。

AC代码

#include<bits/stdc++.h>
using namespace std;
int main(void){
#ifdef ONLINE_JUDGE
#else
    freopen("1.txt","r",stdin);
#endif
    vector<int> a,b;
    int la,lb,k,cnt=0;
    scanf("%d",&la);    a.resize(la);
    for(int i=0;i<la;i++)
        scanf("%d",&a[i]);
    scanf("%d",&lb);    b.resize(lb);
    for(int i=0;i<lb;i++)
        scanf("%d",&b[i]);
    if(la==1&&lb==1){                            //特判每一个序列只有一个数的情况 
        printf("%d",min(a[0],b[0]));
        return 0;
    }
    sort(a.begin(),a.end());                    //对两个序列进行排序 
    sort(b.begin(),b.end());
    int i=0,j=0;
    k=(la+lb)%2==0?(la+lb)/2:(la+lb+1)/2;        //算出中位数在数列中位于第几个，从1开始算的第k个 
    while(1){
        if(i<la&&j<lb){                            //如果两个表都未到头，弹出小的那一个 
            if(a[i]<=b[j])    i++;
            else j++;
        }
        else if(i<la)    i++;                    //如果有任意一个空了，则从不空的里边弹出一个 
        else if (j<lb)     j++;
        cnt++;
        if(cnt==k-1) break;                        //当弹出k-1个的时候，下一个就是第k个了 
    }
    if(i<la&&j<lb)                                //找到第k个的元素在哪个序列中 
        printf("%d",min(a[i],b[j]));
    else if(i<la)
        printf("%d",a[i]);
    else if(j<lb)
        printf("%d",b[j]);
    return 0;
}