欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

0707-二分答案-第k小数

程序员文章站 2022-03-11 20:53:23
...

(上次剩下的两道题,就先放放哈0707-二分答案-第k小数,蒟蒻忙不过来了)

今天又尬到飞起。。。。本来做的时候感觉良好,然后抱了2个0鸭蛋回家。老师说这套题随随便便暴力可以过150分,然后我就凉凉了,真的凉凉了。心灰意凉的我开始好好写博客吧。

这次先上T1(我的题解没有顺序,就是这样任性~)

 

题目描述

有两个正整数数列,元素个数分别为 N 和 M 。从两个数列中分别任取一个数相乘,这样一共可以得到 N*M 个数,询问这 N*M 个数中第 K 小数是多少。(哈,第一眼,so easy。随便排个序就可以了)

输入格式

第一行为三个正整数 N,M 和 K 。
第二行为 N 个正整数,表示第一个数列。
第三行为 M 个正整数,表述第二个数列。
 

输出格式

输出包含一行,一个正整数表示第 K 小数。
 

样例数据 1

输入 
2 3 4 
1 2 
2 1 3
输出

3

样例数据 2

输入 
5 5 18 
7 2 3 5 8 
3 1 3 2 5
输出
16
【数据规模与约定】

0707-二分答案-第k小数

(看到数据范围后的我,渐渐心灰一凉)

没错,这道题的坑就在数据的范围上,要是比较小的话,谁都可以AC。但。。。。

第一想法:数组

结果:哈哈(尬笑。)怎么可能开到1e10去

第二想法:平衡树求第k小数

结果:哈哈x2(尬笑。) 忘了怎么写,而且好像也会超空间限制,毕竟那么多数

第三想法:二分答案

结果:这次不哈哈了。虽然正解大致思路就是这样,但蒟蒻不知道怎么check二分出来的答案,然后就又凉凉了

At last:居然写了一个堆,然后超空间了。。。。(我怎么就不直接暴力呢,还可以多得5分)

那么这时候,正解闪亮登场

上面提到正解使用了二分答案,但问题就在于如何check

下面讲讲思路,首先将a,b两个数组分别进行排序。然后很容易地得出二分答案的上界和下界(r=a[n]*b[m],l=a[1]*b[1]).得到一个mid后,就看比它小的数有多少个(假设为shunxu个),如果shunxu>=k,那么说明现在的mid大了,则r=mid,反之亦然。(详见代码)

那么问题又来了,如何计算比mid小的数有多少个呢?

                                                                                                                                      思考

由于此时a,b已经排好序。那么我们可以枚举a数组里每一个数,用mid\a[i]=num,然后从b数组的末端开始往前扫描,一旦b[top]<=num时,我们就可以往shunxu里加一个top(因为此时从1~top的这些b,与当前的a相乘绝对都不大于mid)。在枚举a数组时,top不会被更新,只会减小(因为b数组是递增的),这样就会节省很多时间,不必每次都从b数组的末端进行重新扫描

至于复杂度,蒟蒻表示不会算(大佬可以自己推,推不来的同学也没关系,至少你知道这很快)

对于解释不太清楚的同学,可以结合代码看一下,蒟蒻的代码可读性很强哦

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
using namespace std;
int n,m,a[200009],b[200009];
long long k;
int check(long long x){//计算x前面有多少数,如果大于k则返回1,否则返回0 
	int top=m;
	long long num,shunxu=0;
	int i;
	for(i=1;i<=n;++i){
		num=x/a[i];
		while(top&&b[top]>num)
			top--;
		shunxu+=top;
	}
	return shunxu>=k;
}
int main(){
	scanf("%d%d",&n,&m);
	scanf("%lld",&k);
	int i,j;
	for(i=1;i<=n;++i)
		scanf("%d",&a[i]);
	for(i=1;i<=m;++i)
		scanf("%d",&b[i]);
	sort(a+1,a+n+1);
	sort(b+1,b+m+1);
	long long l=1ll*a[1]*b[1],r=1ll*a[n]*b[m];//强烈需要注意这里,*1ll是防止int下的a*b溢出,强行转化为long long
	while(l<r){
		long long mid=l+r>>1;
		if(check(mid)) r=mid;
		else l=mid+1;
	}
	printf("%lld",l);
	return 0;
}//计算x前面有多少数,如果大于k则返回1,否则返回0 
	int top=m;
	long long num,shunxu=0;
	int i;
	for(i=1;i<=n;++i){
		num=x/a[i];
		while(top&&b[top]>num)
			top--;
		shunxu+=top;
	}
	return shunxu>=k;
}
int main(){
	scanf("%d%d",&n,&m);
	scanf("%lld",&k);
	int i,j;
	for(i=1;i<=n;++i)
		scanf("%d",&a[i]);
	for(i=1;i<=m;++i)
		scanf("%d",&b[i]);
	sort(a+1,a+n+1);
	sort(b+1,b+m+1);
	long long l=1ll*a[1]*b[1],r=1ll*a[n]*b[m];//强烈需要注意这里,*1ll是防止int下的a*b溢出,强行转化为long long
	while(l<r){
		long long mid=l+r>>1;
		if(check(mid)) r=mid;
		else l=mid+1;
	}
	printf("%lld",l);
	return 0;
}