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

[giscus[bot]]

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

1300. 转变数组后最接近目标值的数组和 标签：数组、二分查找、排序 难度：中等 题目链接 1300. 转变数组后最接近目标值的数组和 - 力扣 题目大意 描述：给定一个整数数组 arr 和一个目标值 target。 要求：返回一个整数 value，使得将数组中所有大于 value 的值变成 value 后，数组的和最接近 target（最接近表示两...

https://algo.itcharge.cn/Solutions/1300-1399/sum-of-mutated-array-closest-to-target/

[Therm4l]

偷懒了，不用二分法。把数组排序后进行处理。以下讨论皆基于排序后进行。

假设前i - 1项的和为pre，当sum超过target的时候，value必定落在arr[i - 1]和arr[i]之间。因此可以列出 cur_sum = pre + (n - i) * arr[i]。这个当算出value的时候，需判断是取value还是value + 1。整个代码如下：

class Solution {
public:
    int findBestValue(vector<int>& arr, int target) {
        int n = arr.size();
        sort(arr.begin(), arr.end());
        int pre = 0;
        for(int i = 0; i < n; i++){
            int cur_sum = pre + (n - i) * arr[i];
            if(cur_sum >= target){
                int value = (target - pre) / (n - i);
                int sum_low = pre + value * (n - i);
                int sum_high = sum_low + n - i;
                if(target - sum_low <= sum_high - target)
                    return value;
                else
                    return value + 1;
            }
            pre += arr[i];
        }
        return arr[n - 1];
    }
};

时间复杂度为 $O(nlogn)$。