时间限制：2 秒

内存限制：128 兆

特殊判题：否

提交：1120

解决：208

题目描述：

给定两个整型数组A和B。我们将A和B中的元素两两相加可以得到数组C。
譬如A为[1,2]，B为[3,4].那么由A和B中的元素两两相加得到的数组C为[4,5,5,6]。
现在给你数组A和B，求由A和B两两相加得到的数组C中，第K小的数字。

输入：

输入可能包含多个测试案例。
对于每个测试案例，输入的第一行为三个整数m，n， k(1<=m,n<=100000， 1<= k <= n *m)：n，m代表将要输入数组A和B的长度。
紧接着两行， 分别有m和n个数， 代表数组A和B中的元素。数组元素范围为[0,1e9]。

输出：

对应每个测试案例，
输出由A和B中元素两两相加得到的数组c中第K小的数字。

样例输入：

2 2 3

1 2

3 4

3 3 4

1 2 7

3 4 5

样例输出：

5

6

来源：

Google面试题

#include <cstdio>

#include <iostream>

#include <algorithm>

using namespace std;

//计算arr1和arr2所有组合相加结果中小于或等于mid的个数

long long judge(long long arr1[],long long m,long long arr2[],long long n,long long mid)

{

    long long cnt=,j=n;

    for(long long i=;i<=m;i++)

    {

        while(j>=&&arr1[i]+arr2[j]>mid)

            j--;

        cnt+=j;

        /* 超时

        for(long long j=1;j<=n;j++)

            if(arr1[i]+arr2[j]<=mid)

                cnt++;

        */

    }

    return cnt;

}

long long find_kth(long long arr1[],long long m,long long arr2[],long long n,long long k)

{

    long long low=arr1[]+arr2[];

    long long high=arr2[m]+arr2[n];

    long long mid;

    while(low<=high)

    {

        mid=(low+high)/;

        long long temp=judge(arr1,m,arr2,n,mid);

        if(k==temp)

            return mid;

        else if(k<temp)

            high=mid-;

        else

            low=mid+;

    }

    return low;

}

int main()

{

    long long m,n,k;

    long long arr1[],arr2[];

    while(scanf("%lld%lld%lld",&m,&n,&k)!=EOF)

    {

        for(long long i=;i<=m;i++)

            scanf("%lld",arr1+i);

        for(long long i=;i<=n;i++)

            scanf("%lld",arr2+i);

        sort(arr1+,arr1+m+);

        sort(arr2+,arr2+n+);

        printf("%lld\n",find_kth(arr1,m,arr2,n,k));

    }

    return ;

}