【51nod1105】【第K大的数】【二分答案】_数组a和数组b,里面都有n个整数。数组c共有n^2个整数,分别是: a[0] * b[0],a[0-CSDN博客

本文链接：https://blog.csdn.net/chunkitlau/article/details/53425088

题目大意

数组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个数。

解题思路

排序后二分答案，由于数的单调性可以o（n）求出有多少个数比当前答案大，再调整区间即可。

#

#include<cmath>
#include<cstdio>
#include<algorithm>
#define LL long long
#define min(a,b) ((a<b)?a:b)
#define max(a,b) ((a>b)?a:b)
#define fo(i,j,k) for(int i=j;i<=k;i++)
#define fd(i,j,k) for(int i=j;i>=k;i--)
using namespace std;
int const maxn=5*1e4;
int n,K;
LL a[maxn+10],b[maxn+10];
int check(LL mx){
    int j=n;LL cnt=0;
    fo(i,1,n){
        for(;a[i]*b[j]>mx;j--);
        cnt+=n-j;
    }
    return cnt+1;
}
int main(){
    scanf("%d%d",&n,&K);
    fo(i,1,n)scanf("%lld%lld",&a[i],&b[i]);
    sort(a+1,a+n+1);
    sort(b+1,b+n+1);
    LL l=1,r=1e18;
    while(l!=r){
        LL mid=(l+r)/2;
        if(check(mid)>K)l=mid+1;
        else r=mid;
    }
    printf("%lld",l);
    return 0;
}