【题解】AT4867 [ABC155D] Pairs

dd_d · 2021-06-20 15:24:40 · 题解

Sol

考虑转换一下题意。
题目中要求我们求第 K 小，实际上就是第 N*(N-1)/2-K+1 大。
考虑二分这个值，记这个值为 mid
分以下情况进行讨论。

• 当 mid<0 时，那么显然，任意 a[i] 为正数或 0 的组合都满足要求。然后对每个 a_i 为正数，a_j 为负数这样的组合进行判断是否大于 mid，这一步操作可以用二分实现，时间复杂度 O(n\ \log\ n)。
• 当 mid=0 时，显然，除了 a_i 为正，a_j 为负的组合其余都满足要求。
• 当 mid>0 时，显然，只有当 a_i 和 a_j 同号时才有可能满足要求。而判断积是否大于 mid 同样可以用二分实现。

具体细节看代码。
代码中用双指针来替代二分。

Code

//LYC_music yyds!
#include<bits/stdc++.h>
#define int long long
using namespace std;
int read()
{
    int pos=1,num=0;
    char ch=getchar();
    while (!isdigit(ch))
    {
        if (ch=='-') pos=-1;
        ch=getchar();
    }
    while (isdigit(ch))
    {
        num=num*10+(int)(ch-'0');
        ch=getchar();
    }
    return pos*num;
}
void write(int x)
{
    if (x<0)
    {
        putchar('-');
        write(-x);
        return;
    }
    if (x>=10) write(x/10);
    putchar(x%10+'0');
}
void writesp(int x)
{
    write(x);
    putchar(' ');
}
void writeln(int x)
{
    write(x);
    putchar('\n');
}
const int N=3e5+1;
int n,k,a[N],l,r,ans,nnn,m,cnt,b[N];
int solve(int x)
{
    int sum=n*(n-1)/2+m*(m-1)/2+cnt*n+cnt*m+cnt*(cnt-1)/2;
    reverse(b+1,b+m+1);
    reverse(a+1,a+n+1);
    for (int i=1,j=n;i<=m;i++)
    {
        while (j>=1&&b[i]*a[j]>=x) 
            j--;
//          cout<<j<<endl;
        sum+=n-j;
    }
    reverse(b+1,b+m+1);
    reverse(a+1,a+n+1);
    return sum;
}
int SOLVE(int x)
{
    int sum=0;
    for (int i=1,j=n;i<=n;i++)
    {
        while (j>=1&&a[i]*a[j]>=x)
            j--;
        sum+=(n-j);
    }
    for (int i=1,j=m;i<=m;i++)
    {
        while (j>=1&&b[i]*b[j]>=x)
            j--;
        sum+=(m-j);
    }
    for (int i=1;i<=n;i++)
        if (a[i]*a[i]>=x) sum--;
    for (int i=1;i<=m;i++)
        if (b[i]*b[i]>=x) sum--;
    return sum/2;
}
bool check(int x)
{
    int ans=0;
    if (x==0) ans=nnn*(nnn-1)/2-n*m;
    if (x<0) ans=solve(x);
    if (x>0) ans=SOLVE(x);
//  writeln(ans);
    return k<=ans;
}
signed main()
{
    nnn=read(); k=read();
    for (int i=1;i<=nnn;i++)
    {
        int x=read();
        if (x>0) a[++n]=x;
        if (x<0) b[++m]=x;
        if (x==0) cnt++;
    }
    sort(a+1,a+n+1);
    sort(b+1,b+m+1,greater<int>());
    k=nnn*(nnn-1)/2-k+1;
    l=-1e18; r=-l;
    while (l<=r)
    {
        int mid=(l+r)>>1;
        if (check(mid))
        {
            l=mid+1;
            ans=mid;
        }
        else r=mid-1;
//      cout<<mid<<' '<<l<<' '<<r<<endl;
//      putchar('\n');
    }
    writeln(ans);
}