红字差评系列1.第K小数

【题目分析】

　　二分答案？smg，我太弱了

//不开longlong wa到挺了

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#define ll long long

const int maxn=;

ll ans=;

ll n,m,k;

ll a[maxn],b[maxn];

ll check(ll x)//找比x大的数有多少个

{

    ll cnt=,p=m;

    for(int i=;i<=n;i++)//枚举每一行有多少个比x小的数

    {

        while((ll)a[i]*b[p]>x&&p)//这里p不需要重置为m，因为ab数组sort过，某一行一定比前一行里找到的p的位置要靠前或者一样

            p--;

        cnt+=p;

    }

    return cnt;

}

int main()

{

    freopen("number.in","r",stdin);

    freopen("number.out","w",stdout);

    scanf("%I64d%I64d%I64d",&n,&m,&k);

    for(int i=;i<=n;i++)

        scanf("%I64d",&a[i]);

    for(int i=;i<=m;i++)

        scanf("%I64d",&b[i]);

    sort(a+,a+n+);

    sort(b+,b+m+);

    ll l=,r=a[n]*b[m];

    while(l<=r)

    {

        ll mid=(l+r)>>;

        if(check(mid)>=k)//如果比mid比实际答案要大

            ans=mid,

            r=mid-;

        else

            l=mid+;

    }

    cout<<ans;

    fclose(stdin);fclose(stdout);

    return ;

}

秒客网

红字差评系列1.第K小数

相关文章