九度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小的数字。

由于题目中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
****************************************************************/
上一篇:Tasks and Back stack 详解


下一篇:LeetCode First Bad Version (二分查找)