题目链接：算法设计与分析-实验2 TopK问题 - Virtual Judge
分析：我们先来看一下数据范围：n<=50000，那么我们肯定不能先求出n^2个乘积，然后再对这些数进行排序，因为这样总的复杂度是n^2*lon(n^2)，肯定会超时，n^2的复杂度也过不去，也就是说我们不可能求出n^2个乘积再对这些乘积进行处理，我们只能利用一些性质来处理这道题目。那我们能不能直接二分答案来求呢？先看下答案的范围，由于元素值是小于等于1e9的，也就是说答案是小于等于1e18的，对答案进行二分的复杂度是log2(1e18)<60,也就是说如果我们能够o(n)判断出来当前判断的值x是否为第k大时我们就能够用这个方法解决这道题目，总的复杂度就是n*60，我们先对a数组和b数组进行从小到大排序，然后我们发现如果a[i]*b[j]>=x,那么一定有a[i]*b[j+1]>=x,也就是说对于每个a[i],我们只要找到第一个b[j]满足a[i]*b[j-1]<x并且a[i]*b[j]>=x，我们就可以知道a[i]参与的n个乘积数中，有n-j+1个数满足乘积数大于等于x，我们怎么找到第一个满足上述条件的b[j]呢？当然这时候肯定能想到lower_bound函数，也就是找b数组中大于等于（x/a[i]的上取整）的第一个b[j],这样判断出来对于每一个a[i]对应的b[j]的复杂度就是nlogn，总的复杂度就是60*nlogn，也可以通过本题，我们有没有办法把logn优化掉呢？其实是可以的，我们先来看一下a[i]和a[i+1]对应的b[j1]和b[j2]有什么关系，首先有a[i]<=a[i+1]和a[i]*b[j1]>=x,那么一定有a[i+1]*b[j1]>=x,又因为b[j2]是第一个令a[i+1]满足a[i+1]*b[j2]>=x的数，所以就有j2<=j1，于是我们就可以用尺取对这一步进行优化，就是每次让j减小，因为满足条件的j是不可能变大的，于是复杂度就变为了60*n，下面分别为两种方法的代码：
lower_bound函数版本：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N=5e4+10;
int a[N],b[N],n,k;
ll cal(ll x)
{
ll cnt=0;
for(int i=n;i>=1;i--)
{
ll t=x/a[i];
if(t*a[i]!=x) t++;
cnt+=(n+1-(lower_bound(b+1,b+n+1,t)-b));
}
return cnt;
}
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
scanf("%d%d",&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+1>>1;
if(cal(mid)>=k) l=mid;
else r=mid-1;
}
cout<<l;
return 0;
}
//22tr-exp2尺取版本：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N=5e4+10;
int a[N],b[N],n,k;
ll cal(ll x)
{
ll cnt=0,j=1;
for(int i=n;i>=1;i--)
{
while(j<=n&&((ll)a[i]*b[j]<x)) j++;//利用单调性优化
cnt+=n-j+1;
}
return cnt;
}
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
scanf("%d%d",&a[i],&b[i]);
sort(a+1,a+n+1);
sort(b+1,b+n+1);
ll l=(ll)a[1]*b[1],r=(ll)a[n]*b[n];//设置边界(防止越界，先转化为long long)
while(l<r)
{
ll mid=l+r+1>>1;
if(cal(mid)>=k) l=mid;
else r=mid-1;
}
cout<<l;
return 0;
}
//22tr-exp2
