自动搬运

查看原文

来自洛谷，原作者为

	Fyq_20 **

搬运于2025-08-24 23:10:47，当前版本为作者最后更新于2025-03-10 14:45:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题解：[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;
}