讨论/题目交流/🐱 第 16 场夜喵双周赛/
🐱 第 16 场夜喵双周赛
展开讨论

第二题坑了我蛮久的,但又不想用穷举,直到结束前才答出来。拿出来做个参考:

更新:这个解法发现是有错误的,正在考虑优化: 输入 [1,1,1,6,9], 18 时返回的是 7,正确应该是 9。


class Solution {
    public int findBestValue(int[] arr, int target) {
        int len = arr.length;
        int aimVal = getClosetVal(target, len);
        
        // 所有小于等于目标值的一定保留
        int sum = 0, size = 0;
        for(int val : arr) {
            if (val <= aimVal) {
                sum += val;
                size++;
            }
        }
        
        // 所有值都保留时(目标值大于等于整个数组和),取数组最大值
        if (len == size) {
            Arrays.sort(arr);
            return arr[arr.length - 1];
        }
        // 剩下的值重新计算最接近的取值即可
        return getClosetVal(target - sum, len - size);
    }
    
    // 计算 num 个值求和最接近 target 值时的取值
    private int getClosetVal(int target, int num) {
        return (target%num) > (num/2) ? target/num + 1 : target/num;
    }
}
展开全部 8 讨论