知名做网站,wordpress建公司官网,天门网页设计,企业营销型网站分析题目
在一条数线上有 NQNQ 个点 A1,…,AN,B1,…,BQA1,…,AN,B1,…,BQ #xff0c;其中点 AiAi 的坐标为 aiai #xff0c;点 BjBj 的坐标为 bjbj 。
就每个点 j1,2,…,Qj1,2,…,Q 回答下面的问题#xff1a;
设 XX 是 A1,A2,…,ANA1,A2,…,AN 中最…题目
在一条数线上有 NQNQ 个点 A1,…,AN,B1,…,BQA1,…,AN,B1,…,BQ 其中点 AiAi 的坐标为 aiai 点 BjBj 的坐标为 bjbj 。
就每个点 j1,2,…,Qj1,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≤1081≤kj≤N1≤kj≤N所有输入值均为整数。
做法
题目就是让我们求离b的第k近的距离是多少。我们的思路就是给a排序然后找到b所在的位置然后往b的左右两边算他的第k近的数。但这样往b的左右两边一个一个看会超时。我们就二分b往两边的距离看a数组有多少个在b-mid到bmid的范围内。如果个数小于k那么范围小了lmid否则rmid。最后输出r即可。
#includebits/stdc.h
using namespace std;
int n,q;
long long a[100010];
int main(){scanf(%d%d,n,q);for(int i1;in;i) scanf(%lld,a[i]);sort(a1,a1n);for(int i1;iq;i){long long b;int k;scanf(%lld%d,b,k);if(ba[1]){//特判coutabs(b-a[k])endl;continue;}else if(ba[n]){coutabs(b-a[n1-k])endl;continue;}long long l-1e18-10,r1e1810;//也可以不用这么大2e8就行while(l1r){long long midl(r-l)/2;int id1lower_bound(a1,a1n,b-mid)-a;int id2upper_bound(a1,a1n,bmid)-a;if(id2-id1k){rmid;}else{lmid;}}coutrendl;}
}
