AT_abc364_d 题解

ikunTLE · 2024-07-30 20:33:32 · 题解

题目传送门

思路

这道题用二分答案。题目中的 A_i 表示的是数轴上的第 i 个点，不保证其升序，所以要先将数组 A 排序。

设每一次二分的点为 mid，分别求出与 b-mid 和 b+mid 距离最近的点，并判断其差是否 \ge k。

注意事项

• 二分的右边界要开大，建议 2\times10^8。

AC CODE

#include<bits/stdc++.h>
using namespace std;
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
const int N=1e5+10,R=2e8;
int n,q,a[N];
int check(int x,int b,int k){
    int l=lower_bound(a+1,a+n+1,b-x)-a;
    int r=upper_bound(a+1,a+n+1,b+x)-a;
    return r-l>=k;
}
int main(){
    n=read(),q=read();
    for(int i=1;i<=n;++i)
        a[i]=read();
    sort(a+1,a+n+1);
    while(q--){
        int b=read(),k=read(),l=0,r=R;
        while(l<=r){
            int mid=(l+r)>>1;
            if(!check(mid,b,k))
                l=mid+1;
            else r=mid-1;
        }
        printf("%d\n",l);
    }
    return 0;
}