题目描述

难度分:$1845$

输入$n(2 \leq n \leq 2 \times 10^5)$，$k(1 \leq k \leq \frac{n \times (n-1)}{2})$和长为$n$的数组$a(-10^9 \leq a[i] \leq 10^9)$。

从$a$中选两个数，相乘，一共可以得到$\frac{n \times (n-1)}{2}$个结果。

输出这$\frac{n \times (n-1)}{2}$个数中，第$k$小的数。

注：$k=1$表示最小的数。

输入样例$1$

4 3
3 3 -4 -2

输出样例$1$

-6

输入样例$2$

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

输出样例$2$

6

输入样例$3$

30 413
-170202098 -268409015 537203564 983211703 21608710 -443999067 -937727165 -97596546 -372334013 398994917 -972141167 798607104 -949068442 -959948616 37909651 0 886627544 -20098238 0 -948955241 0 -214720580 277222296 -18897162 834475626 0 -425610555 110117526 663621752 0

输出样例$3$

448283280358331064

算法

二分答案

很容易看出来二分答案的思路，给定一个$limit$，计算$a$中小于$limit$的数的个数$cnt$，最后一个满足$cnt \lt k$的数就是答案。

主要的难点在于$cnt$怎么求？将$a$先升序排列，然后枚举数对中的较小数$a[i]$（$i \in [1,n)$），计算它的右边有多少个数$a[j]$（$j \in (i,n]$）能够满足$a[i] \times a[j] \lt limit$。分为以下几种情况：

1. $a[i] \lt 0$时：
   $(1)$ $limit \gt 0$，所有满足$a[j] \geq 0$的数都符合要求。部分负数$a[j] \lt 0$满足要求，$a[j]$越大，$a[i] \times a[j]$就越小，因此可以通过二分确定出第一个满足$a[i] \times a[j] \lt limit$的$j$，能够贡献$nidx-j+1$（$nidx$是最后一个负数的索引）。
   $(2)$ $limit \lt 0$，$a[i]$要和正数相乘才有可能比$limit$小，而正数越大，与$a[i]$相乘的结果越小，因此也是二分找到第一个满足条件的正数$a[j]$，能够贡献$n-j+1$。
   $(3)$ $limit = 0$，所有正数都可以，能够贡献$n-pidx+1$（$pidx$是第一个正数的索引）。

2. $a[i] \gt 0$时，由于它的右边只有正数，只可能在$limit \gt 0$时有解，二分找到最后一个满足$a[i] \times a[j] \lt limit$的正数$a[j]$即可，能够贡献$j-i$。

3. $a[i]=0$时，右边只有非负数，也是$limit \gt 0$时有解，右边所有数和$a[i]$相乘都得$0$，都满足要求，能够贡献$n-i$。

计算所有$a[i]$以上几种情况的贡献就可以求出能与它配对，且满足$a[i] \times a[j] \lt limit$的$a[j]$个数。

复杂度分析

时间复杂度

最外层二分的时间复杂度为$O(log_2A)$，其中$A$表示上下界之差，最大可以跨越长整型的范围。$check$函数中如果用双指针算法，就是$O(n)$的时间复杂度，由于我双指针经常写错，所以又套了个二分，时间复杂度为$O(nlog_2n)$，算法整体的时间复杂度为$O(log_2Anlog_2n)$。

空间复杂度

在二分的过程中只使用了有限几个变量，额外空间复杂度就是排序的空间复杂度，快排的空间复杂度为$O(log_2n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;

const int N = 200010;
int n, zidx, pidx, nidx;
LL a[N], k;

LL get_min() {
    if(a[1] <= 0 && a[n] <= 0) {
        return a[n - 1]*a[n];
    }else if(a[1] >= 0 && a[n] >= 0) {
        return a[1]*a[2];
    }else {
        return a[1]*a[n];
    }
}

LL get_max() {
    if(a[1] <= 0 && a[n] <= 0) {
        return a[1]*a[2];
    }else if(a[1] >= 0 && a[n] >= 0) {
        return a[n - 1]*a[n];
    }else {
        return max(a[1]*a[2], a[n - 1]*a[n]);
    }
}

LL check(LL limit) {
    LL cnt = 0;
    for(int i = 1; i < n; i++) {
        if(a[i] < 0) {
            if(limit > 0) {
                // a[i]和非负数相乘都比limit小
                cnt += n - nidx;
                int l = i + 1, r = nidx, j = -1;
                while(l <= r) {
                    int mid = l + r >> 1;
                    if(a[mid]*a[i] < limit) {
                        j = mid;
                        r = mid - 1;
                    }else {
                        l = mid + 1;
                    }
                }
                if(j != -1) cnt += nidx - j + 1;
            }else if(limit < 0) {
                // a[i]要和正数相乘才能比limit小
                if(pidx != -1) {
                    int l = pidx, r = n, j = -1;
                    while(l <= r) {
                        int mid = l + r >> 1;
                        if(a[i]*a[mid] < limit) {
                            j = mid;
                            r = mid - 1;
                        }else {
                            l = mid + 1;
                        }
                    }
                    if(j != -1) cnt += n - j + 1;
                }
            }else {
                // limit=0时，只有正数和a[i]相乘才能比limit小
                if(pidx != -1) cnt += n - pidx + 1;
            }
        }else if(a[i] > 0) {       // 右边只有正数
            if(limit > 0) {
                int l = i + 1, r = n, j = -1;
                while(l <= r) {
                    int mid = l + r >> 1;
                    if(a[mid]*a[i] < limit) {
                        j = mid;
                        l = mid + 1;
                    }else {
                        r = mid - 1;
                    }
                }
                if(j != -1) cnt += j - i;
            }
        }else {
            // a[i]=0，右边只有非负数
            if(limit > 0) {
                cnt += n - i;
            }
        }
    }
    return cnt;
}

int main() {
    scanf("%d%lld", &n, &k);
    for(int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
    }
    sort(a + 1, a + n + 1);
    zidx = -1;     // 第一个零的位置
    pidx = -1;     // 第一个正数的位置
    nidx = -1;     // 最后一个负数的位置
    for(int i = 1; i <= n; i++) {
        if(a[i] == 0 && zidx == -1) {
            zidx = i;
        }
        if(a[i] > 0 && pidx == -1) {
            pidx = i;
        }
        if(a[i] < 0) {
            nidx = i;
        }
    }
    LL left = get_min(), right = get_max();
    while(left < right) {
        LL mid = left + right + 1 >> 1;
        if(check(mid) < k) {
            left = mid;
        }else {
            right = mid - 1;
        }
    }
    printf("%lld\n", right);
    return 0;
}