Description
有两个非负整数数列，元素个数分别为N和M。从两个数列中分别任取一个数相乘，这样一共可以得到NM个数，询问这NM个数中第K小数是多少。
时间限制为20ms 。
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
比较傻逼的题,沙茶都能想到二分答案k,然后计算有多少(a[i]*b[j]<=k)的点对.
计算也水的一比,给a,b排个序,然后在a中枚举i,可以知道j在b中是一段(1~j'),这一段中都可以满足.
然后因为随着i递增j递减,check就是O(n+m)的了.
// It is made by XZZ
// Fei Fan Ya Xi Lie~~~
#include<cstdio>
#include<algorithm>
using namespace std;
#define il inline
#define rg register
#define vd void
typedef int mainint;
#define int long long
typedef long long ll;
il int gi(){
rg int x=0,f=1;rg char ch=getchar();
while(ch<'0'||ch>'9')f=ch=='-'?-1:f,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*f;
}
const int maxn=20001;
int a[maxn],b[maxn],n,m,k;
il ll check(int num){
int r=m,ret=0;
for(rg int l=1;l<=n;++l){
while(r&&a[l]*b[r]>num)--r;
if(r==0)break;
ret+=r;
}
return ret;
}
mainint main(){
n=gi(),m=gi(),k=gi();
for(rg int i=1;i<=n;++i)a[i]=gi();
for(rg int i=1;i<=m;++i)b[i]=gi();
sort(a+1,a+n+1),sort(b+1,b+m+1);
ll l=a[1]*b[1],r=a[n]*b[m],mid;
while(l<r){
mid=(l+r)>>1;
if(check(mid)>=k)r=mid;
else l=mid+1;
}
printf("%lld
",l);
return 0;
}