给出一个长度为 n 的数列 和一个长度为 m 的数列 ，可以构造得到一个 n×m 的矩阵 C，其中 C​i,j​​ =A​i​​ ×Bj​​ 。

给出整数 K，你需要求出 C 中第 K 大的数的值。

输入格式：
第一行输入三个整数 n,m,K(1≤n,m≤10​5​​ ,1≤K≤n×m)。

第二行输入 n 个空格隔开的整数 A​1​​ ,…,A​n​​ (−10​6​​ ≤A​i​​ ≤10​6​​ )

第三行输入 m 个空格隔开的整数 B​1​​ ,…,B​m​​ (−10​6​​ ≤B​i​​ ≤10​6​​ )

输出格式
输出一行一个整数，表示矩阵中的第 K 大的数的值。

输入样例：
3 3 3
2 3 4
4 5 6

输出样例：
18

题解：二分答案，二分求出大于答案的乘积的个数。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<cstdlib>
#include<map>
#include<set>
#define ll long long
#define llu unsigned ll
#define ld long double
#define pr make_pair
#define pb push_back
#define x first
#define y second
#define int ll
using namespace std;
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const int mod=1e9+7;
const int maxn=100100;
int a[maxn],b[maxn];
int n,m,k;

int check1(int i,int mid)
{
    int l=0,r=m;
    int pos=0;
    int tm=0;
    while(l<=r)
    {

        tm=(l+r)>>1;
        if(a[i]*b[tm]>=mid) pos=tm,l=tm+1;
        else r=tm-1;
    }
    return pos;
}

int check2(int i,int mid)
{
    int l=0,r=m;
    int pos=0;
    int tm=0;
    while(l<=r)
    {
        tm=(l+r)>>1;
        if(a[i]*b[tm]>=mid) pos=tm,r=tm-1;
        else l=tm+1;
    }
    return (m-pos);
}

int check(int mid)
{
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        if(a[i]<=0) ans+=check1(i,mid);
        else ans+=check2(i,mid);
    }
    return ans;
}

signed main(void)
{
    scanf("%lld%lld%lld",&n,&m,&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+n+1);
    sort(b+1,b+m+1);
    b[0]=-lnf/1e6;
    b[++m]=lnf/1e6;
    int l=-1e12,r=1e12;
    int pos=0;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(check(mid)>=k) pos=mid,l=mid+1;
        else r=mid-1;
    }
    printf("%lld\n",pos);
    return 0;
}