蓝桥杯2022年第十三届省赛真题-最少刷题数(二分-java)

解题思路: 

时间复杂度：O(N*log(max(A))*logN)

二分找需要刷题数目a， 设已经刷了多少题为x，再二分找符合 < a + x - 1 与 > a + x + 1 的人数，根据题目要求比较即可。

有错误欢迎指出！

注意事项:

参考代码:

import java.util.*;
import java.io.*;
public class Main{
    static int[] a, b;
    static int n;
    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
	public static void main(String[] args) throws IOException{

		n = Integer.parseInt(reader.readLine());
        String[] s = reader.readLine().split(" ");
        a = new int[n];
        b = new int[n];
        for(int i = 0; i < n; i++){
            a[i] = Integer.parseInt(s[i]);    
            b[i] = a[i];
        }
        Arrays.sort(b);
        
        int[] res = new int[n];
        for(int i = 0; i < n; i++) {
            res[i] = getMin(a[i]);
        }
        
        for(int i = 0; i < n; i++) {
            log.write(res[i] + " ");
        }
		
		// 释放资源
        reader.close();
        log.flush();
        log.close();
	}
    
    //lowerBound
	public static int getMin(int nums) {
	    int l = 0, r = b[n - 1];
	    while(l < r) {
	        int mid = l + r >> 1;
	        if(getR(nums + mid - 1, mid) < getL(nums + mid + 1)) {
	            l = mid + 1;
	        } else {
	            r = mid;
	        }
	    }
	    return l;
	}
	
	public static int getR(int tar, int e) {
	    int l = 0, r = n - 1;
	    while(l < r) {
	        int mid = l + r + 1>> 1;
	        if(b[mid] <= tar) {
	            l = mid;
	        } else {
	            r = mid - 1;
	        }
	    }
	    return e == 0 ? l + 1 : l;
	}
	
	public static int getL(int tar) {
	    int l = 0, r = n - 1;
	    while(l < r) {
	        int mid = l + r >> 1;
	        if(b[mid] < tar) {
	            l = mid + 1;
	        } else {
	            r = mid;
	        }
	    }
	    return tar > b[n - 1] ? 0 : n - l;
	}
}