9度OJ月赛-题目1534：数组中第K小的数字 （二分搜索）

九度OJ月赛---题目1534：数组中第K小的数字 （二分搜索）

题目描述：

给定两个整型数组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 31 23 43 3 41 2 73 4 5

样例输出：

56

来源：

Google面试题

代码：二分搜索，countnum计算两个数组元素和小于等于二分值的个数：

#include <cstdio>#include <cstdlib>#include <algorithm>using namespace std;typedef long long lld; const int INF=1000000000; const int MAX=110000;lld a[MAX],b[MAX];lld countnum(lld mid,lld n,lld m){       lld res=0;       lld i=0,j=m-1;       for(i=0;i<n;i++)       {              while(j>=0&&a[i]+b[j]>mid)              {                     j--;              }              res+=j+1;       }       return res;}int main(){         lld n,m,k;       int last=0;       int i,j;       lld ans=0;       while(scanf("%lld%lld%lld",&n,&m,&k)!=EOF)       {              for(i=0;i<n;i++)  scanf("%lld",&a[i]);              for(i=0;i<m;i++)  scanf("%lld",&b[i]);                sort(a,a+n);              sort(b,b+m);                            lld low=a[0]+b[0];              lld high=a[n-1]+b[m-1];              lld mid;              while(low<high)              {                     mid=(low+high)>>1;                     if(countnum(mid,n,m)>=k)                     {                            high=mid;                     }                     else low=mid+1;              }              printf("%lld\n",low);       }    return 0;}