题解：P11849 [TOIP 2023] 裁员风暴

· · 题解

题解：[TOIP 2023]裁员风暴

题目大意：

在给定数组 a_n 中，找到所有 a_i 和 \frac{a_i+a_j}{2}\ (i\neq j) 中的第 k 大的数。

主要思路：二分答案+双指针判定

首先将选择一个的情况视为选择了两个一样的数，这样题目就变成了在 a_n 中找到所有 \frac{a_i+a_j}{2} 中的第 k 大的数。

先确定主算法是二分，然后考虑如何求比一个数 x 大的 \frac{a_i+a_j}{2} 的个数。
容易想到首先给数组排序，得到单调不降的数组，然后枚举左界 l，此时可以使 \frac{a_l+a_r}{2}<x 的最大右界 r 在 l 增加时不会增加（l=r+1，即比 x 小的数集为 \varnothing 时除外）。于是在枚举 l 时实时更新 r，并得到较小数为 a_l 时比 x 大的 \frac{a_i+a_j}{2} 的个数 n-r，此时 \sum_{l=1}^{n}n-r 就是比 x 大的\frac{a_i+a_j}{2} 的个数。

最后正常二分答案，特判分子是否可以被 2 整除分别输出即可。注意如果二分的是答案的 2 倍需要开long long。

code:

#include<bits/stdc++.h>
using namespace std;
#define int long long//不是什么好习惯
int n,k;
int p[200005];
bool check(int x)
{
    int pos=0;
    int l=1,r=n;
    for(l;l<=n;l++)
    {
        if(r<l)r=l-1;
        //注意如果之前r被更新到小于l
        //需要赋值为l-1
        //否则会计重。
        while(p[l]+p[r]>=x&&r>=l)r--;
        pos+=n-r;
    }
    return pos<k;
}
signed main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>p[i];
    sort(p+1,p+n+1);
    int l=-2e9,r=2e9;//这里二分的是答案的2倍
    while(l<r)
    {
        int mid=l+r+1;
        mid>>=1;
        if(check(mid))r=mid-1;
        else l=mid;
    }
    if(l%2==0)cout<<l/2<<endl<<1<<endl;
    else cout<<l<<endl<<2<<endl;//特判l和2互质
    return 0;
}