Atcoder - 155D Pairs

传送门：Atcoder - 155D

题目描述

N个整数，每两两组合相乘得到一个数，第K大的数是多少。

输入描述

$2≤N≤2*10^5$
$-10^9≤a_i≤10^9$

输出描述

输出第K大的数

思路分析

很容易想到二分答案，二分过程中再二分查找小于等于mid的数有多少

样例输入

10 40
5 4 3 2 -1 0 0 0 0     

样例输出

6

AC代码

#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <functional>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <iomanip>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define fun function
#define vi vector<int>
#define lowbit(x) x&(-x)
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

using namespace std;

const int INF = 0x3f3f3f3f;
const int N=1e6;


ll a[N];

int main() {
    IOS;
#ifdef xiaofan
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif

    ll n,k;
    cin>>n>>k;
    for(int i=0; i<n; i++)
        cin>>a[i];
    sort(a,a+n);

    ll L=-1e18-7,R=1e18+7;
    while(R-L>1) {
        ll Mid=(L+R)/2;
        ll cnt=0;
        for(int i=0; i<n; i++) {
            if(a[i]<0) {
                int l=i,r=n;
                while(r-l>1) {
                    int mid=(l+r)/2;
                    if(a[i]*a[mid]<=Mid) r=mid;
                    else l=mid;
                }
                cnt+=n-r;
            } else {
                int l=i,r=n;
                while(r-l>1) {
                    int mid=(l+r)/2;
                    if(a[i]*a[mid]<=Mid) l=mid;
                    else r=mid;
                }
                cnt+=l-i;
            }
        }

        if(cnt<k)L=Mid;
        else R=Mid;

    }
    cout<<R<<endl;

    return 0;
}