ABC364:D - K-th Nearest(二分)

题目

在一条数线上有 N+QN+Q 个点 A1,…,AN,B1,…,BQA1​,…,AN​,B1​,…,BQ​ ，其中点 AiAi​ 的坐标为 aiai​ ，点 BjBj​ 的坐标为 bjbj​ 。

就每个点 j=1,2,…,Qj=1,2,…,Q 回答下面的问题：

• 设 XX 是 A1,A2,…,ANA1​,A2​,…,AN​ 中最接近点 BjBj​ 的 kjkj​ -th 点。求点 XX 与 BjBj​ 之间的距离。更正式地说，设 didi​ 是点 AiAi​ 与 BjBj​ 之间的距离。将 (d1,d2,…,dN)(d1​,d2​,…,dN​) 按升序排序，得到序列 (d1′,d2′,…,dN′)(d1′​,d2′​,…,dN′​) 。求 dkj′dkj​′​ .

限制因素

• 1≤N,Q≤1051≤N,Q≤105
• −108≤ai,bj≤108−108≤ai​,bj​≤108
• 1≤kj≤N1≤kj​≤N
• 所有输入值均为整数。

做法

题目就是让我们求离b的第k近的距离是多少。我们的思路就是给a排序，然后找到b所在的位置，然后往b的左右两边算他的第k近的数。但这样往b的左右两边一个一个看会超时。我们就二分b往两边的距离，看a数组有多少个在b-mid到b+mid的范围内。如果个数小于k，那么范围小了，l=mid，否则r=mid。最后输出r即可。

#include<bits/stdc++.h> 
using namespace std;
int n,q;
long long a[100010];
int main(){scanf("%d%d",&n,&q);for(int i=1;i<=n;i++) scanf("%lld",&a[i]);sort(a+1,a+1+n);for(int i=1;i<=q;i++){long long b;int k;scanf("%lld%d",&b,&k);if(b<=a[1]){//特判cout<<abs(b-a[k])<<endl;continue;}else if(b>=a[n]){cout<<abs(b-a[n+1-k])<<endl;continue;}long long l=-1e18-10,r=1e18+10;//也可以不用这么大，2e8就行while(l+1<r){long long mid=l+(r-l)/2;int id1=lower_bound(a+1,a+1+n,b-mid)-a;int id2=upper_bound(a+1,a+1+n,b+mid)-a;if(id2-id1>=k){r=mid;}else{l=mid;}}cout<<r<<endl;}
}