Visit Counter
AmazingCounters.com

1、题目大意:给定两个序列,定义c[i][j] = a[i] * b[j],求c数组里的第k大
2、分析:最开始看成第k小了。。。。。。。
这道题用二分第k大是啥,然后nlogn的判定
怎么判定呢》》》》》枚举a数组,然后在b数组里二分查找使得a[i] * b[j] <= 啥的最大k值
然后就过了。。。。。
3、代码:

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
#define LL long long
LL a[100010], b[100010];
LL n, m, k;
bool cmp(const int &x, const int &y){
    return x > y;
}
bool u(LL x, LL y){
    LL ret = 0;
    for(int i = 1; i <= n; i ++){
        LL l = 1, r = m + 1;
        while(l < r){
            LL mid = (l + r) / 2;
            if(mid == l) mid ++;
            if(a[i] * b[mid] >= x) l = mid;
            else r = mid - 1;
        }
        if(a[i] * b[1] < x) continue;
        ret += l;
    }
    if(ret < y) return true;
    else return false;
}
int main(){
    while(scanf("%lld%lld%lld", &n, &m, &k) != EOF){
        for(int i = 1; i <= n; i ++) scanf("%lld", &a[i]);
        for(int i = 1; i <= m; i ++) scanf("%lld", &b[i]);
        sort(b + 1, b + m + 1, cmp);
        LL l = 0, r = 214748364711111111ll;
        while(l < r){
            LL mid = (l + r) / 2;
            if(mid == l) mid ++;
            if(u(mid, k)) r = mid - 1;
            else l = mid;
        }
        printf("%lld\n", l);
    }
    return 0;
}

4、分类:二分