51nod 1105 第K大的数

二分法。
二分套二分。很好玩的一个题目。
把两个数组排序
先二分结果，再去判断这个结果是不是第k大。判断时候枚举a数组里面的值，二分查找b数组里面最小可以和当前枚举的a数组里面的值相乘大于第一层二分的结果，比如说a[i] * b[j] > k(二分的结果), 那么j后面的所有数都和a[i]相乘都比k大，最后统计一下有多少个比k大

#include<cstdio>
#include<algorithm>
using namespace std;

typedef long long ll;
const int maxn = 1e5;
ll a[maxn];
ll b[maxn];
ll n, m;

int judge(ll k){
    int tot = 0;
    for(int i = 1; i <= n; i++){
        int l = 1, r = n;
        while(l < r){
            int mid = (l + r) >> 1;
            if(a[i] * b[mid] > k){
                r = mid;
            }else l = mid + 1;
        }
        if(a[i] * b[l] > k) tot += n - l + 1;
    }
    return tot <= m - 1;
}

int main(){
    scanf("%lld%lld", &n, &m);
    for(int i = 1; i <= n; i++){
        scanf("%d%d", &a[i], &b[i]);
    }
    sort(a + 1, a + n + 1);
    sort(b + 1, b + n + 1);
    ll l = 0, r = a[n] * b[n], ans;
    while(l <= r){
        ll mid = (l + r) >> 1;
        if(judge(mid)){
            r = mid - 1;
            ans = mid;
        }else l = mid + 1;
    }
    printf("%lld\n", ans);
    return 0;
}