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

题目链接：http://ac.jobdu.com/problem.php?pid=1534

题目大意：给出两个长度分别为M和N的数组a，b，从两个数组中各任选一个相加，将和放入一个新数组c，现在问新数组从小到大排序后第K个数是多大。 m，n， k(1<=m,n<=100000， 1<= k <= n *m) 数组元素整型范围

解题思路：c数组大小为N*M，而且数组元素有2e9这么大，存不下，复杂度高，乍一看无法入手，但是我们思考一下会发现，对于一个数X，c数组中小于等于它的个数其实是可以在0(N+M)时间内算出来的：

将a，b两个数组排序后，假设对于a中第i个元素a[i]与b中第j个元素b[j]相加小于等于X，即a[i]+b[j] <= x 并且a[i] + b[j+1] > x，那么对于i+1来说, a[i+1] + b[j+1] > x 一定成立。那么我们便可以枚举a中每个元素，计算出其与b中多少个元素相加小于等于x，累加之后便得到c中小于等于X的数的个数。复杂度最坏为O(N+M)，不算大。

所以，我们只需要二分最小值和最大值之间的数字检测即可，复杂度O(Nlog2e9)。

代码：

 1 const int maxn = 1e5 + 10;
 2 int n, m;
 3 ll k;
 4 ll a[maxn], b[maxn];
 5 
 6 ll check(int x){
 7     int i = 0, j = m - 1;
 8     ll ans = 0;
 9     for(; i < n; i++){
10         while(j >= 0 && a[i] + b[j] > x) 
11             j--;
12         if(j < 0) break;
13         ans += j + 1;
14     }
15     return ans;
16 }
17 void solve(){
18     sort(a, a + n);
19     sort(b, b + m);
20     ll l = a[0] + b[0], r = a[n - 1] + b[m - 1];
21     while(l <= r){
22         ll mid = (l + r) >> 1;
23         if(check(mid) < k) l = mid + 1;
24         else r = mid - 1;
25     }
26     printf("%lld
", l);
27 }
28 
29 int main(){
30     whi

题目：

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

时间限制：2 秒

内存限制：128 兆

特殊判题：否

提交：2012

解决：438

题目描述：: 给定两个整型数组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小的数字。

样例输入：

样例输出：

5
6

来源：: Google面试题