链接

https://leetcode-cn.com/problems/sum-of-mutated-array-closest-to-target/

文章截图

简评

今天做了一道算法题，以前遇到这种没有思路的算法题我肯定是看答案的，但是今天没有，就是因为前些天我看的这篇文章，那篇文章给我的启示就是“先给出解决方案，再谈优化”。今天这道算法题我就是这样，把头脑中的模糊想法一步步具象化成代码思路，最后实现（没有进一步优化）。即使这个思路很暴力，很没有“算法”的感觉。我也发了解题思路，有兴趣的话看这里。题解截图见下方

代码：

class Solution {
    public int findBestValue(int[] arr, int target) {
        int allSum = 0;
        int max = 0;
        for (int value : arr) {
            allSum += value;

            if (max < value) {
                max = value;
            }
        }

        int allAverage = target / arr.length;

        if (allSum <= target) {
            return max;
        } else {
            // 小于平均数的数字之和
            int lowerAverageSum = 0;
            // 大于平均数的应该有的总和
            int higherAverageSum = target;
            // 大于平均数的数字个数
            int higherCount = 0;
            for (int value : arr) {
                if (value <= allAverage) {
                    lowerAverageSum += value;
                    higherAverageSum -= value;
                } else {
                    higherCount++;
                }
            }

            // 向下取整的答案
            int downResult = higherAverageSum / higherCount;
            // 向上取整的答案
            int upResult = downResult + 1;

            int[] newArr = new int[higherCount];

            boolean shouldContinue = false;
            int i = 0;
            for (int value : arr) {
                // 如果还有比downResult小的数，那需要递归的把大于平均值的数再做一遍计算
                if (value > allAverage && value < downResult) {
                    shouldContinue = true;
                }

                if (value > allAverage) {
                    newArr[i++] = value;
                }
            }

            if (shouldContinue) {
                return findBestValue(newArr, higherAverageSum);
            }

            // 和target的差
            int downDiff = target - (lowerAverageSum + downResult * higherCount);
            int upDiff = (lowerAverageSum + upResult * higherCount) - target;

            // 取差小的
            if (downDiff <= upDiff) {
                return downResult;
            } else {
                return upResult;
            }
        }
    }
}