杭电5178 (二分练习！)

杨鹏伟

发布于 2020-09-11 15:05:32

2930

发布于 2020-09-11 15:05:32

文章被收录于专栏：ypwypw

pairs John has n points on the X axis, and their coordinates are (x[i],0),(i=0,1,2,…,n−1). He wants to know how many pairs<a,b> that |x[b]−x[a]|≤k.(a<b)

The first line contains a single integer T (about 5), indicating the number of cases. Each test case begins with two integers n,k(1≤n≤100000,1≤k≤109). Next n lines contain an integer xi, means the X coordinates.

For each case, output an integer means how many pairs<a,b> that |x[b]−x[a]|≤k.

题意：就是能找到多少对啊a[i],a[j] 满足 a[j] -a[i] <= k.;

思路：首先你肯定能想到要将其排序，然后得话，如果我们从小的开始找，就每次二分就行了！

#include<bits/stdc++.h>
#define maxn 300000+100
using namespace std;
typedef long long ll;

int  a[maxn];
int n,k;
int t;
ll num; 

int bs(int l,int r,int tag){
	int mid,ans=0;
	while(l <= r && r < n){
		mid = (l+r)/2;
		if(a[mid] <= tag){
			ans += mid -l+1;
			l = mid +1;
		}
		else{
			r = mid - 1;
		}
	}
	return ans;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>t;
	while(t--){
		num = 0;
		cin>>n>>k;
		for(int i=0;i<n;i++){
			cin>>a[i];
		}
		sort(a,a+n);
		for(int i=0;i<n;i++)
		 num += bs(i+1,n-1,a[i]+k);
		 
		cout<<num<<endl;
	}
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2020-02-08 ，如有侵权请联系 cloudcommunity@tencent.com 删除

axis