ABC155D

StevenLiTheOIer · 2023-03-22 09:30:46 · 题解

思路：

二分答案。

我们考虑怎么写 check 函数。对于一个数 x，二分出有多少个数乘 a_i 的积小于 x，最后把答案除以 2，看是否小于 k。

但是因为 a_i 分正负数和 0，分类讨论：

所以需要原数组 a 的倒序数组 b，用来对负数二分。

详细请见代码。

Code：

#include <bits/stdc++.h>
using namespace std;
long long n, k, offset, a[200006], b[200006];
int lowerbound(long long x, long long y) //二分正数
{
    int l = 1, r = n, pos = 0;
    while (l <= r)
    {
        int mid = l + r >> 1;
        if (a[y] * a[mid] < x) l = mid + 1, pos = mid;
        else r = mid - 1;
    }
    return pos >= y ? pos - 1 : pos; //当 pos >= y 时，出现了 a[y] * a[y] < x，所以要减 1，下同
}
int upperbound(long long x, long long y) //二分负数
{
    int l = 1, r = n, pos = 0;
    while (l <= r)
    {
        int mid = l + r >> 1;
        if (a[y] * b[mid] < x) l = mid + 1, pos = mid;
        else r = mid - 1;
    }
    return pos >= n - y + 1 ? pos - 1 : pos;
}
bool check(long long x)
{
    long long cnt = 0;
    for (int i = 1; i < offset; i++)
        cnt += upperbound(x, i);
    for (int i = offset; i <= n; i++)
        cnt += lowerbound(x, i);
    return cnt / 2 <= k - 1;
}
int main()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    sort(a + 1, a + n + 1);
    offset = n + 1;
    for (int i = 1; i <= n; i++)
    {
        if (a[i] >= 0)
        {
            offset = i; //找出正负数的分界点
            break;
        }
    }
    for (int i = 1; i <= n; i++)
        b[n - i + 1] = a[i];
    long long l = -1ll * 1e18, r = 1e18; //单个数范围是1e9，乘积的范围是[-1e18, 1e18]
    while (l <= r) //比较标准的二分答案
    {
        long long mid = l + r >> 1;
        if (!check(mid)) r = mid - 1;
        else l = mid + 1;
    }
    cout << r << endl;
    return 0;
}