100043. 【NOIP2017提高A组模拟7.13】第K小数

Description

有两个正整数数列，元素个数分别为N和M。从两个数列中分别任取一个数相乘，这样一共可以得到N*M个数，询问这N*M个数中第K小数是多少。

Input

输入文件包含三行。
第一行为三个正整数N,M和K。
第二行为N个正整数，表示第一个数列。
第三行为M个正整数，表述第二个数列。

Output

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

Sample Input

Sample1:
2 3 4
1 2
2 1 3
Sample2:
5 5 18
7 2 3 5 8
3 1 3 2 5

Sample Output

Sample1:
3
Sample2:
16

Data Constraint

Solution

二分答案，判断小于答案的数的个数。

1.如果判断严格小于mid的数的个数<k则说明mid太小

直接判断即可。

2.如果判断小于等于mid的数的个数>=k则说明mid太大

注意这里a的相同值可能有多个，在统计时等于mid的个数时  相同的a  的 答案要用数组记录下来。

 

Code1

#include<cstdio>
#include<cstring>
#include<algorithm>
#define I int
#define ll long long
#define F(i,a,b) for(I i=a;i<=b;i++)
#define Fd(i,a,b) for(I i=a;i>=b;i--)
#define mem(a,b) memset(a,b,sizeof(a))
#define N 200003
using namespace std;
ll n,m,k,a[N],b[N],tot,s[N],l,r,mid,ans;

void R(ll &x){
	x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
}
I check(ll x){
	tot=0;
	mem(s,0);
	I j=m;
	F(i,1,n){
		if(a[i]==a[i-1]) s[i]=s[i-1];
		while(j&&a[i]*b[j]>=x){
			if(a[i]*b[j]==x) s[i]++;//可能a有相同的数 
			j--;
		}
		tot+=j+s[i];
	}
	return tot+s[0]>=k;
}
I main(){
	freopen("knum.in","r",stdin);
	freopen("knum.out","w",stdout);
	R(n),R(m),R(k);
	F(i,1,n) R(a[i]);
	sort(a+1,a+1+n);
	F(i,1,m) R(b[i]);
	sort(b+1,b+1+m);
	for(l=0,r=a[n]*b[m];l<=r;){
		mid=l+r>>1;
		(check(mid))?r=(ans=mid)-1:l=mid+1;
	}
	printf("%lld\n",ans);
	return 0;
}

Code2

#include<cstdio>
#include<cstring>
#include<algorithm>
#define I int
#define ll long long
#define F(i,a,b) for(I i=a;i<=b;i++)
#define N 200003
using namespace std;
ll n,m,k,a[N],b[N],tot,s,l,r,mid,ans;

void R(ll &x){
	x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
}
I check(ll x){
	tot=s=0;
	I j=m;
	F(i,1,n){
		while(j&&a[i]*b[j]>=x) j--;
		tot+=j;
	}
	return tot<k;
}
I main(){
	R(n),R(m),R(k);
	F(i,1,n) R(a[i]);
	sort(a+1,a+1+n);
	F(i,1,m) R(b[i]);
	sort(b+1,b+1+m);
	for(l=0,r=a[n]*b[m];l<=r;){
		mid=l+r>>1;
		(check(mid))?l=(ans=mid)+1:r=mid-1;
	}
	printf("%lld\n",ans);
	return 0;
}