[1300. 转变数组后最接近目标值的数组和]

[1300. 转变数组后最接近目标值的数组和]

给你一个整数数组 arr 和一个目标值 target ，请你返回一个整数 value ，使得将数组中所有大于 value 的值变成 value 后，数组的和最接近 target （最接近表示两者之差的绝对值最小）。

如果有多种使得和最接近 target 的方案，请你返回这些整数中的最小值。

请注意，答案不一定是 arr 中的数字。

示例 1：

输入：arr = [4,9,3], target = 10
输出：3
解释：当选择 value 为 3 时，数组会变成 [3, 3, 3]，和为 9 ，这是最接近 target 的方案。

示例 2：

输入：arr = [2,3,5], target = 10
输出：5

示例 3：

输入：arr = [60864,25176,27249,21296,20204], target = 56803
输出：11361

提示：

• 1 <= arr.length <= 10^4
• 1 <= arr[i], target <= 10^5

public int findBestValue(int[] arr, int target) {
    //从小到大排序
        Arrays.sort(arr);
    //计算前缀和
        int sum = 0;
	
        for (int i = 0; i < arr.length; i++) {
            //计算还未加上部分的最佳平均值，当小数部分等于0.5时，只能向左取值
            int x = (int)( (double)(target-sum)/(arr.length-i)+0.499999);
			
            //如果平均值小于等于当前值，也就是说后续的值只会越来越大，截断值为当前平均值最接近target
            if(x <= arr[i]){
                return x;
            }
            sum += arr[i];
        }
    //此时说明数组所有值相加小于target,返回数组最大值
        return arr[arr.length-1];
    }

另一种思路是二分查找截断值，可以很容易找到两个边界，target/arr.size() 和 arr.max(),如果target/arr.size() 大于 arr.max()，说明数组和小于target，返回arr.max()

 public int findBestValue(int[] arr, int target) {

        int average = (int)( (double)target/arr.length+0.49999);
        int max = 0;
        for (int i : arr) {
            if(i > max) {
                max = i;
            }
        }

        if(max < average){
            return max;
        }

        int sum = 0;
        while (average < max){
            sum = 0;
            int median = (average+max)/2;
            for (int i : arr) {
                if(i > median) {
                    sum += median;
                }else {
                    sum += i;
                }
            }
            if(sum <= target){
                average = median+1;
            }else {
                max = median;
            }
        }
        sum = 0;
        for (int i : arr) {
            if(i > average){
                sum += average;
            }else {
                sum += i;
            }
        }

        int tmp = 0;
        for (int i : arr) {
            if(i > average-1){
                tmp += average-1;
            }else {
                tmp += i;
            }
        }

        if(Math.abs(target - tmp) >Math.abs(sum - target)){
            return average;
        }else {
            return average-1;
        }
    }