学步园

题目链接~~>

解题思路：

                 我们可以看出，二个数组的和  min  =  a[ 0 ] + b [ 0 ]  ,  max  =  a[  n - 1] + b [ m - 1] ,这样我们就可以二分枚举这个区间的所有数，枚举每个数的时候判断它是第几大，你可能会问：怎样判断第几大？？？ 假如你要查找  x 是第几大，那么可以对比 a 数组中的每个数，让其在 b 数组中查找不大于  x - a[ i ]  (这里 x >= a[i ])的数，有几个就表示 a[ i ] 分别加b数组中的这几个数的和小于
x , 这样遍历 a 数组就可以找到  x  在所有的和中是第几大。

代码：

#include<iostream>
#include<fstream>
#include<iomanip>
#include<ctime>
#include<fstream>
#include<sstream>
#include<stack>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<cstdio>
#include<algorithm>
#define INT long long int
using namespace std ;
const double esp = 0.00000001 ;
const INT INF = 9999999 ;
const INT mod = 1e9 + 7 ;
const INT MY = 100 + 10 ;
const INT MX = 100000 + 10 ;
INT n ,m ,k ;
INT a[MX] ,b[MX] ;
INT count(INT mx)
{
    INT cnt = 0 ;
    for(INT i = 0 ;i < n ; ++i)
    {
        if(a[i] > mx) break ;
        cnt += upper_bound(b ,b+m ,mx-a[i]) - b ;
    }
    return cnt ;
}
INT binary_search()
{
    INT mid ,le = a[0] + b[0] ,rt = a[n-1] + b[m-1] ;
    while(le < rt)
    {
        mid = (rt+le)/2 ;
        if(count(mid) >= k)  rt = mid ;
        else   le = mid + 1 ;
    }
    return le ;
}
void input()
{
    for(INT i = 0 ;i < n ; ++i)
        scanf("%lld" ,&a[i]) ;
    for(INT i = 0 ;i < m ; ++i)
        scanf("%lld" ,&b[i]) ;
    sort(a ,a+n) ;
    sort(b ,b+m) ;
}
int main()
{
    while(~scanf("%lld%lld%lld" ,&n ,&m ,&k))
    {
        input() ;
        cout<<binary_search()<<endl ;
    }
    return 0 ;
}
 

题目链接~~>

解题思路：这题和上面那题一样，只不过加改为了乘。

代码：

#include<iostream>
#include<fstream>
#include<iomanip>
#include<ctime>
#include<fstream>
#include<sstream>
#include<stack>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<cstdio>
#include<algorithm>
#define INT __int64
using namespace std ;
const double esp = 0.00000001 ;
const INT INF = 9999999 ;
const INT mod = 1e9 + 7 ;
const INT MY = 100 + 10 ;
const INT MX = 5000 + 10 ;
INT n ,m ,k ;
INT binary_search(INT mid)
{
    INT cnt= 0 ;
    for(INT i = 1 ;i <= n ; ++i)
    {
        if(mid < i)  break ;
        if(mid/i <= m)
                cnt += mid/i ;
        else    cnt += m ;
    }
    return cnt ;
}
int main()
{
    INT le ,rt ,mid ;
    while(~scanf("%I64d%I64d%I64d" ,&n ,&m ,&k))
    {
        if(n > m)  swap(n ,m) ;
        le = 1 ; rt = n*m ;
        while(le < rt)
        {
            mid = (rt+le)/2 ;
            INT mx = binary_search(mid) ;
            if(mx >= k)
                   rt = mid ;
            else   le = mid+1 ;
        }
        cout<<le<<endl ;
    }
    return 0 ;
}