ABC-364-D - K-th Nearest · znzryb

## AC代码

这题思路就是二分答案，二分可能的dis并检验

在复杂的就是check()函数必须在logn的级别，写的时候也比较复杂，这边简单阐述一下

```cpp
ll l=lower_bound(A.begin(),A.end(),obl)-A.begin();
ll r=upper_bound(A.begin(),A.end(),obr)-A.begin();
// 这种方法找到的应该是该dis能包括的最多点数
```

这个代码是用来找到该dis可以包含的最多点数，详见下面图解

![image](https://media.znzryb.com/20241108-bcd4b7cb/image_f38a20c3.png)

b=2 , dis=3，包含的最多点数就是-1，-1，5，5，即4个点，在图上很清楚，upper_bound-lower_bound就是4。

然后我们知道，最多点≥k是可能满足条件的（可能最少点符合条件），但最多点<k，那么一定不符合条件

AC

[](https://atcoder.jp/contests/abc364/submissions/59526172)

```cpp
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>

using namespace std;
typedef long long ll;
const ll N=static_cast<ll>(1e5)+10;
ll n,q,rangeA;
vector<ll> A;

inline bool check(ll b,ll dis,ll k) {
    ll obl=b-dis,obr=b+dis;
    // 这种方法找到的应该是该dis能包括的最多点数
    ll l=lower_bound(A.begin(),A.end(),obl)-A.begin();
    ll r=upper_bound(A.begin(),A.end(),obr)-A.begin();
    if(r-l<k)      // 如果最多点数都<k 不用多说，铁不符合
        return false;
    return true;
}

inline ll bsearch(ll b,ll k) {
    ll l=0,r=rangeA;
    while (l<r) {
        ll mid= l+r >>1;
        if(check(b,mid,k))
            r=mid;
        else
            l=mid+1;
    }
    return l;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++) {
        ll a;
        cin>>a;
        A.push_back(a);
    }
    sort(A.begin(),A.end());
    for(int i=1;i<=q;i++) {
        ll b,k;
        cin>>b>>k;
        // 其实应该叫rangeDis最好，即二分查找的范围，不会超过b点与两端点之间的最大距离
        rangeA=max(abs(b-A[0]),abs(b-A[n-1]));
        cout<<bsearch(b,k)<<'\n';
    }
}
// AC https://atcoder.jp/contests/abc364/submissions/59526172
```

## 心路历程（WA，TLE，MLE……）