pairs

Problem Description

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)

Input

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 

x[i](−109≤x[i]≤109), means the X coordinates

Output

For each case, output an integer means how many pairs

<a,b> that 

|x[b]−x[a]|≤k.

Sample Input

2 5 5 -100 0 100 101 102 5 300 -100 0 100 101 102

Sample Output

3 10

解题新知：

①题意：给你N个数分别为x0,x1,……xn-1，给你一个数K，询问你满足|xb-xa|<k   （a<b）情况有几种

②思路：题意很简单，如果暴力枚举，复杂度为O(n^2)，肯定超时。那么我们可以用二分的思想，找到满足|xb-xa|的极限位置

AC代码：

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;long long x[100005];int main(){    int t;    scanf("%d",&t);    while(t--)    {        int n,k;        scanf("%d %d",&n,&k);        for(int i=0;i
         
          k) //寻找比x[i]大的极限位置                    r=mid-1;                else                    l=mid+1;            }            num=num+r-i;        }        cout<
          
           <