D - Pairs

题目描述

图片说明

分析

我们知道这题的元素是,所以两个数的乘积就是,所以我们可以在范围二分输出答案。

举个例子


此数列中，,
假如我们现在二分到了mid = b这个值，第K个值指向这个位置，那么我们只要去判断小于mid的元素个数是否<K，若是则l = mid,之后l会一只往右移动，当仍保持这小于l的元素个数<K,最终l会因为二分走到，不会再离开这个区间了。而r最终也会遇到l，l == r

坑点

由于此题我是二分套二分的思路，而我大量使用了lower_bound和upper_bound，花了很长时间也没调出来，后来是手写的二分，结果还是调了很久，最后发现需要手动处理掉边界情况，也可叫特殊情况，一定要让二分里面有解！！！！才去二分

AC代码

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
ll N,K;
ll arr[1000010];

bool judge(ll x){
    ll cnt = 0;
    for(int i = 1;i<N;i++){
        if(arr[i]>=0){
            ll l = i+1,r = N,mid;
            if(arr[i]*arr[l]>=x) continue;//二分中无解的情况
            while(l<r){
                mid = (l+r+1)>>1;
                if(arr[i]*arr[mid] < x) l = mid;
                else r = mid-1;
            }
            cnt += l-i;
        }else{ //和负数乘会变号，情况和上面相反
            ll l = i+1,r = N,mid;
            if(arr[i]*arr[N] >= x) continue;//二分中无解的情况
            if(arr[i]*arr[l]<x){//特殊情况
                cnt += N-l+1;
                continue;
            }
            while(l<r){
                mid = (l+r+1)>>1;
                if(arr[i]*arr[mid] >= x) l = mid;
                else r = mid-1;
            }
            cnt += N-l;
        }
    }
    return cnt < K;
}

int main(){
    cin>>N>>K;
    for(int i = 1;i<=N;i++) scanf("%lld",&arr[i]);
    sort(arr+1,arr+N+1);
    ll l = -1e18-10,r = 1e18+10,mid;
    while(l<r){
        mid = (l+r+1)>>1;
        if(judge(mid)) l = mid;
        else r = mid-1;
    }
    cout<<l<<endl;
    return 0;
}