51nod 1105 第K大的数 （二分套二分 好题）

传送门：51nod 1105

Input示例

3 2
1 2
2 3
3 4

Output示例

9

思路：一看到题目，还以为是主席树求区间第 K 大值的题……然鹅是求 a、b 两数组相乘的值中第 K 大的。由于 N 很大，不能暴力求解，时间和空间都受不了。

一百度，原来有种二分套二分的方法是求解两个数组组合乘积的第 K 大值的。具体方法是先对 a、b 数组排序，然后外层对可能出现在 c 数组中的值 mid 进行二分，内层用二分求 c 数组中 >= 该值 mid 的数的个数，找到一个满足条件的最大值即答案。

注意：

1.数据很大，要用 long long 型。当两个 int 型整数相乘超过 int 型的值时需要至少两者之一是 long long 型，这时候只有最终值设为 long long 型是不行的哦~

2.对于二分搜索想再说几句。个人建议写二分的时候使用“左闭右开”的形式，例如，要对下标为 0~n-1 的 n 个数二分，则传参时保证左闭右开，即区间左端为0，右端为n。在判断二分终止条件时也是左闭右开，即 while( l < r ) .对于缩小区间时，也是左闭右开，即 if( a[mid] < val ) l=mid+1; if( a[mid] > val) r=mid;

其他形式不一定有错，但是上面这种是比较容易记忆的，一定没错。

代码：

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;

LL a[50010],b[50010];

LL find(LL x,int n)
{ //查找c数组中 >=x 数的个数 
	int i,num;
	LL tp,sum=0;
	for(i=n-1;i>=0;i--)
	{ //枚举a数组，寻找a[i]*b[j]中 <x 数的个数num 
		if(x%a[i]) tp=x/a[i]+1;
		else tp=x/a[i];
		num=lower_bound(b,b+n,tp)-b;
		sum+=n-num;
		if(sum==0) break;
	}
	return sum;
}

int main()
{
	int i,n,k;
	LL l,r,mid,tmp;
	while(~scanf("%d%d",&n,&k))
	{
		for(i=0;i<n;i++) scanf("%d%d",&a[i],&b[i]);
		sort(a,a+n);
		sort(b,b+n);
		l=a[0]*b[0]; //l为c数组中最小的数 
		r=a[n-1]*b[n-1]+1; //r为c数组中最大的数 
		while(l<r)
		{ //二分 
			mid=(l+r)>>1;
			tmp=find(mid,n); //查找 >=mid 数的个数 
			if(tmp<k) r=mid; //如果个数<k，说明当前数太大 
			else l=mid+1;
		}
		printf("%lld\n",l-1);
	}
	return 0;
}

看完代码了，你是不是和我一样，感觉有些地方好像看起来挺对的，但是想不通为什么是这样呢？

1.外层二分的时候 mid 的值一定会在 c 数组中吗？

其实在二分的过程中不一定能保证每个 mid 的值都在 c 数组中，我们只是用 mid 值来不断的逼近答案，答案ans一定是使得 c 数组中 >=ans 数的个数有 k 个的最大值。

2.内层二分的时候为什么要判断 x 是否能整除 a[i]?

原因很简单，因为我们要用 lower_bound 函数找的是 a[i]*b[j] < x 数的个数，如果 x%a[i]==0 直接找 < x%a[i] 的个数就好了，反之需要找 < x%a[i] + 1 的个数。