Description
有两个非负整数数列，元素个数分别为N和M。从两个数列中分别任取一个数相乘，这样一共可以得到N*M个数，询问这N*M个数中第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
Hint
Source
二分 /单调性
source JZOJ 100043
鸣谢陈思宇制作数据！
Solution
我们先对于a、b数组分别排一次序，使这两个数组都具有单调性。
考虑二分答案。
假设现在二分到了mid，那么前k小的数都应满足a[i]*b[j]≤mid。
现在，我们要枚举i和j使得mid满足上述条件。
考虑如何快速地算出j。
由于a、b数组都具有了单调性，因此我们得到的j也是单调递减的，就可以利用单调性轻松求出j。
所以我们得出的算法的时间复杂度为O(N*log(最大的数))，轻松通过！
Code
#include <bits/stdc++.h>
#define int long long using namespace std; inline int read()//快读
{
int f = , x = ;
char c = getchar(); while (c < '' || c > '')
{
if (c == '-')
f = -;
c = getchar();
} while (c >= '' && c <= '')
{
x = x * + c - '';
c = getchar();
} return f * x;
} int n, m, k, a[], b[]; signed main()
{
n = read(), m = read(), k = read(); for (register int i = ; i <= n; i++)
{
a[i] = read();
} for (register int i = ; i <= m; i++)
{
b[i] = read();
} sort(a + , a + + n);//排序
sort(b + , b + + m); int l = , r = a[n] * b[m]; while (l < r)//二分
{
int mid = (l + r) >> , sum = ; for (register int i = , j = m; i <= n; i++, sum = sum + j)//枚举i,并且计算满足条件的个数
{
while (a[i] * b[j] > mid)//如果满足条件
{
--j;//每次更新j
}
} if (sum >= k)//如果答案比k大
{
r = mid;//缩小最大值范围
}
else
{
l = mid + ;//否则更新最小值
}
} printf("%lld", l);//输出符合条件的答案个数 return ;//结束
}