数组中第K小的数字（Google面试题）

http://ac.jobdu.com/problem.php?pid=1534

题目1534：数组中第K小的数字

时间限制：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=0,j=n;
    for(long long i=1;i<=m;i++)
    {
        
        while(j>=1&&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[1]+arr2[1];
    long long high=arr2[m]+arr2[n];
    long long mid;
    while(low<=high)
    {
        mid=(low+high)/2;
        long long temp=judge(arr1,m,arr2,n,mid);
        if(k==temp)
            return mid;
        else if(k<temp)
            high=mid-1;
        else
            low=mid+1;
    }
    return low;
}
int main()
{
    long long m,n,k;
    long long arr1[100001],arr2[100001];
    while(scanf("%lld%lld%lld",&m,&n,&k)!=EOF)
    {
        for(long long i=1;i<=m;i++)
            scanf("%lld",arr1+i);
        for(long long i=1;i<=n;i++)
            scanf("%lld",arr2+i);
        sort(arr1+1,arr1+m+1);
        sort(arr2+1,arr2+n+1);
        printf("%lld
",find_kth(arr1,m,arr2,n,k));
    }
    return 0;
}