題目

在一條數(shù)線上有?N+QN+Q?個點?A1,…,AN,B1,…,BQA1?,…,AN?,B1?,…,BQ??，其中點?AiAi??的坐標(biāo)為?aiai??，點?BjBj??的坐標(biāo)為?bjbj??。

就每個點?j=1,2,…,Qj=1,2,…,Q?回答下面的問題：

• 設(shè)?XX?是?A1,A2,…,ANA1?,A2?,…,AN??中最接近點?BjBj??的?kjkj??-th 點。求點?XX?與?BjBj??之間的距離。更正式地說，設(shè)?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
• 所有輸入值均為整數(shù)。

做法

題目就是讓我們求離b的第k近的距離是多少。我們的思路就是給a排序，然后找到b所在的位置，然后往b的左右兩邊算他的第k近的數(shù)。但這樣往b的左右兩邊一個一個看會超時。我們就二分b往兩邊的距離，看a數(shù)組有多少個在b-mid到b+mid的范圍內(nèi)。如果個數(shù)小于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;}
}