二分法和快排搞定了

灬Amiya灬 · 2018-11-16 20:07:20 · 题解

一开始java用暴力过不了，不知道是不是没有剪枝呢 没有确认，然后因为比较少写二分，想锻炼下，便写一下吧 写二分的话，边界问题要注意好 快排好后，从左到右遍历点， find函数处理遍历的点，向左二分搜索，得出离自己最远的在d范围里面的点。 然后用算出之间包括自己有多少个点就可以得出有多少对了。

package p1296;

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int n,d;
    static int count=0;
    public static void main(String[] args) {
        // TODO 自动生成的方法存根
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        d = in.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++) {
            a[i] =  in.nextInt();
        }
        Arrays.sort(a);
        for(int i=0;i<n;i++) {
            count+=i-find(0,i,i,a);
        }
        System.out.println(count);
    }
    private static int find(int left,int right,int i,int a[]) {
        // TODO 自动生成的方法存根
        int mid = (right+left)/2;
        if(left==right) {
            if(a[i]-a[left]<=d) {
                return left;
            }
            else return left+1;
        }
        if(a[i]-a[mid]<=d) {
             return find(left,mid,i,a);
        }
        else return find(mid+1,right,i,a);

    }

}