JAVA二分版,过了两个其他全部WA,不知道问题在哪,求解
查看原帖
JAVA二分版,过了两个其他全部WA,不知道问题在哪,求解
592424
stLOVEyxx楼主2023/4/16 06:04
import java.io.*;
import java.util.Arrays;

public class Main {

    private static int N,C;

    private static StreamTokenizer st;

    private static PrintWriter pw;

    public static void main(String[] args) {
        int[] arr = new int[(int)2e5+5];
        st = new StreamTokenizer(new BufferedReader(new
                InputStreamReader(System.in)));
        pw = new PrintWriter(new BufferedWriter(new
                OutputStreamWriter(System.out)));
        N = nextInt();
        C = nextInt();
        for(int i = 0;i < N;i++) {
            arr[i] = nextInt();
        }
        Arrays.sort(arr);
        long count = 0;
        for(int i = 0;i < N;i++) {
            int leftIndex = binary_search(arr,arr[i] - C,false);
            if(leftIndex == -1)
                continue;
            int rightIndex = binary_search(arr,arr[i] - C,true) - 1;
            count += rightIndex - leftIndex + 1;
        }
        pw.print(count);
        pw.flush();
    }

    private static int binary_search(int[] arr1, int target,boolean flag) {
        int l = -1,r = N;
        while(l + 1 < r) {
            int mid = ((r - l) >> 1) + l;
            if(arr1[mid] < target || flag && arr1[mid] <= target)
                l = mid;
            else
                r = mid;
        }
        if(r < N && arr1[r] == target || l > -1 && arr1[l] == target)
            return r;
        else
            return -1;
    }

    private static int nextInt() {
        try {
            st.nextToken();
        }catch (IOException e) {
            e.printStackTrace();
        }
        return (int)st.nval;
    }
}
2023/4/16 06:04
加载中...