乘法（二分套二分）

题意：一个长度为n的数列，和一个长度为m的数列，每项相乘的出来的所有结果中第k大的值，其中数列长度为1e5,整数大小1e6
思路：先二分要求的值，再定住每一个矩阵n，去二分另一个矩阵m，得出大于等于这个值的个数，直到找到这个k即可。
时间复杂度（O（nlogn^2））

#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)
    {
   
        //cout<<"l: "<<l<<" r: "<<r<<endl;
        tm=(l+r)>>1;
        if(a[i]*b[tm]>=mid) pos=tm,r=tm-1;
        else l=tm+1;
    }
    //cout<<"mid: "<<mid<<endl;
    //cout<<"pos: "<<pos<<endl;
    //cout<<"a[i]: "<<a[i]<<endl;
    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);
    }
    //cout<<"ans: "<<ans<<endl;
    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;
        //cout<<"mid: "<<mid<<endl;
    }
    printf("%lld\n",pos);
    return 0;
}