给定两个整型数组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小的数字。

由于题目中a，b两个数组的size很大，因此暴力枚举肯定是不行的。我用了二分去逼近解， 假设给定一个解，可以用二分求出这个解在c这个数组中排第几，如果排名大于等于k，说明这个解可能更小，如果小于k那么说明这个解不够大。这样最终得到的结果即时解。

#include <cstdio>#include <string>#include <cstring>#include <iostream>#include <algorithm>using namespace std; long long int a[100099];long long int b[100099];long long n, m, k; bool C(long long int mid, long long int k){    long long int cnt = 0;    for (int i=0; i<n; i++)    {        if (mid < a[i] ) continue;        long long tar = mid - a[i];        long long pos1 = upper_bound(b, b + m, tar) - b;        //cout << pos << endl;        cnt += pos1;    }     if ( cnt >= k ) return true;    return false;} int main(){       while ( scanf("%lld%lld%lld", &n, &m, &k)!=EOF )    {        for (int i=0; i<n; i++) scanf("%lld", &a[i]);        for (int i=0; i<m; i++) scanf("%lld", &b[i]);        sort(a, a+n);        sort(b, b+m);         long long l = a[0] + b[0], h = a[n-1] + b[m-1];        while (l + 1 < h)        {            long long int mid = (l + h) >> 1;            if ( C(mid, k) ) {h = mid;}            else l = mid;        }        printf("%lld\n", h);    } } /**************************************************************    Problem: 1534    User: frostcake    Language: C++    Result: Accepted    Time:1620 ms    Memory:3084 kb****************************************************************/