题目:数组A和数组B,里面都有n个整数。数组C共有n^2个整数,分别是A[0] * B[0],A[0] * B[1] ......A[1] * B[0],A[1] * B[1]......A[n - 1] * B[n - 1](数组A同数组B的组合)。求数组C中第K大的数。

例如:A:1 2 3,B:2 3 4。A与B组合成的C包括2 3 4 4 6 8 6 9 12共9个数。


题解:二分好题,最重要的一点是要想到,一个数是第K大,那么必定有K个数大于或者等于它(但是这里我觉得有个毛病,就是出现重复的数被看作是不同大的,题目难道不应该保证组合后不出现重复吗?)。然后就是再二分答案,二分答案的情况就是检查比当前答案大的数是否大于K个,所以这里又要二分找和b[i]组合的个数。但是再想想,还有一个问题,这样计算出来的答案真的是a[i]和b[i]组合出来的答案吗,会不会出现比他大的值?其实不会,因为我们在用当前答案除以a[i]去获取b[i]的值的时候是向上取整的。如果一个数大于他,那么取得的b[i]值必然大于正确答案应该取的值,所以这里保证了不会出现不存在的值。


代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=50005;
LL n, k, a[maxn], b[maxn];
bool check(LL ans){
    LL cnt=0;
    for(int i=n-1;i>=0;i--){
        LL num=ans/a[i];
        if(ans%a[i])num++;
        cnt+=n-(lower_bound(b, b+n, num)-b);
    }
    return cnt>=k;
}
int main()
{
    scanf("%lld%lld", &n, &k);
    for(int i=0;i<n;i++){
        scanf("%lld%lld", &a[i],&b[i]);
    }
    sort(a, a+n);
    sort(b, b+n);
    LL l=a[0]*b[0], r=a[n-1]*a[n-1], mid;
    while(l<=r){
        mid=(l+r)/2;
        if(check(mid))l=mid+1;
        else r=mid-1;
    }
    printf("%lld\n", l-1);
    return 0;
}