牛客 - 乘法(二分套二分)

题目链接：点击查看

题目大意：给出一个n*m的矩阵，每个位置的元素为 maze [ i ] [ j ] = a [ i ] * b [ j ]，现在给出数组 a 和数组 b ，求出矩阵中第k大的数

题目分析：首先别读错题了，第k大的意思是第n*m+1-k小的数，我们可以转换一下比较方便理解，给出数组 a 和数组 b 后，我们可以排序处理，因为涉及到负数的关系，直接计算的话无法保证其单调性，所以我们可以分类讨论，在main函数中二分答案，对于每个答案找一下有多少个数小于等于当前答案，寻找的方法我们可以用遍历+二分的方法找，注意要分大于零，小于零和等于零的情况，这样总的时间复杂度为nlognlogn，光理论不好说清楚，看看代码估计就明白了

代码：

#include<iostream>
#include<cstdio> 
#include<string>
#include<ctime>
#include<cstring>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<cmath>
#include<sstream>
#include<unordered_map>
using namespace std;
 
typedef long long LL;
 
const int inf=0x3f3f3f3f;
 
const int N=1e5+100;

LL n,m,k,a[N],b[N];

bool check(LL x)
{
	LL cnt=0;
	for(int i=1;i<=n;i++)//枚举数组a的每个元素，当数组a确定后，a*b就有单调性了
	{
		if(a[i]==0)
		{
			if(x>=0)
				cnt+=m;
		}
		else if(a[i]>0)//如果a>0，那么a*b的单调性与b相同
		{
			int l=1,r=m,ans=0;
			while(l<=r)//二分有多少个数小于等于答案
			{
				int mid=l+r>>1;
				if(a[i]*b[mid]<=x)
				{
					ans=mid;
					l=mid+1;
				}
				else
					r=mid-1;
			}
			cnt+=ans;
		}
		else if(a[i]<0)//如果a<0，那么a*b的单调性与b相反
		{
			int l=1,r=m,ans=m+1;
			while(l<=r)
			{
				int mid=l+r>>1;
				if(a[i]*b[mid]<=x)//二分有多少个数小于等于答案
				{
					ans=mid;
					r=mid-1;
				}
				else
					l=mid+1;
			}
			cnt+=m+1-ans;
		}
	}
	return cnt>=k;
}

int main()
{
//	freopen("input.txt","r",stdin);
//	ios::sync_with_stdio(false);
	scanf("%lld%lld%lld",&n,&m,&k);
	k=n*m+1-k;
	for(int i=1;i<=n;i++)
		scanf("%lld",a+i);
	for(int i=1;i<=m;i++)
		scanf("%lld",b+i);
	sort(a+1,a+1+n);
	sort(b+1,b+1+m);
	LL l=-1e12,r=1e12,ans;
	while(l<=r)//二分答案
	{
		LL mid=l+r>>1;
		if(check(mid))
		{
			ans=mid;
			r=mid-1;
		}
		else
			l=mid+1;
	}
	printf("%lld\n",ans);
	
 
 
 
	
	
	
	
	
	
	
	
	
	return 0;
}