数组A和数组B,里面都有n个整数。
数组C共有n^2个整数,分别是:
A[0] * B[0],A[0] * B[1] ...... A[0] * B[n-1]
A[1] * B[0],A[1] * B[1] ...... A[1] * B[n-1]
......
A[n - 1] * B[0],A[n - 1] * B[1] ...... A[n - 1] * B[n - 1]
是数组A同数组B的组合,求数组C中第K大的数。
#include<bits/stdc++.h>
using namespace std;
const int N=5e4+10;
int a[N],b[N],k,n;
typedef long long ll;
ll check(ll x){
//枚举a数组
ll cnt=0;
for(int i=1;i<=n;i++){
ll t=x/a[i];
if(t*a[i]!=x) t++;//当x=7 时 除以a[2]除不尽,
int x1=lower_bound(b+1,b+1+n,t)-b;
cnt+=n+1-x1;
}
return cnt;
}
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++){
scanf("%d%d",&a[i],&b[i]);
}
sort(a+1,a+1+n);
sort(b+1,b+1+n);
ll l=0,r=1e18;
// cout<<check(9)<<endl;
// cout<<check(4)<<endl;
// cout<<check(7)<<endl;
while(l<r){
ll mid=l+r+1>>1;
if(check(mid)>=k){
l=mid;//在所有a[i]*b[i]的结果中比mid大的数至少有k个
}else r=mid-1;
}
printf("%lld\n",l);
}
4316 树状数组