# [1300. Sum of Mutated Array Closest to Target](https://leetcode.com/problems/sum-of-mutated-array-closest-to-target/)



## 题目

Given an integer array `arr` and a target value `target`, return the integer `value` such that when we change all the integers larger than `value` in the given array to be equal to `value`, the sum of the array gets as close as possible (in absolute difference) to `target`.

In case of a tie, return the minimum such integer.

Notice that the answer is not neccesarilly a number from `arr`.

**Example 1**:

```
Input: arr = [4,9,3], target = 10
Output: 3
Explanation: When using 3 arr converts to [3, 3, 3] which sums 9 and that's the optimal answer.
```

**Example 2**:

```
Input: arr = [2,3,5], target = 10
Output: 5
```

**Example 3**:

```
Input: arr = [60864,25176,27249,21296,20204], target = 56803
Output: 11361
```

**Constraints**:

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


## 题目大意

给你一个整数数组 arr 和一个目标值 target ，请你返回一个整数 value ，使得将数组中所有大于 value 的值变成 value 后，数组的和最接近  target （最接近表示两者之差的绝对值最小）。如果有多种使得和最接近 target 的方案，请你返回这些整数中的最小值。请注意，答案不一定是 arr 中的数字。

提示：

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



## 解题思路

- 给出一个数组 arr 和 target。能否找到一个 value 值，使得将数组中所有大于 value 的值变成 value 后，数组的和最接近 target。如果有多种方法，输出 value 值最小的。
- 这一题可以用二分搜索来求解。最后输出的唯一解有 2 个限制条件，一个是变化后的数组和最接近 target 。另一个是输出的 value 是所有可能方法中最小值。二分搜索最终的 value 值。mid 就是尝试的 value 值，每选择一次 mid，就算一次总和，和 target 比较。由于数组里面每个数和 mid 差距各不相同，所以每次调整 mid 有可能出现 mid 选小了以后，距离 target 反而更大了；mid 选大了以后，距离 target 反而更小了。这里的解决办法是，把 value 上下方可能的值都拿出来比较一下。

## 代码

```go

func findBestValue(arr []int, target int) int {
	low, high := 0, 100000
	for low < high {
		mid := low + (high-low)>>1
		if calculateSum(arr, mid) < target {
			low = mid + 1
		} else {
			high = mid
		}
	}
	if high == 100000 {
		res := 0
		for _, num := range arr {
			if res < num {
				res = num
			}
		}
		return res
	}
	// 比较阈值线分别定在 left - 1 和 left 的时候与 target 的接近程度
	sum1, sum2 := calculateSum(arr, low-1), calculateSum(arr, low)
	if target-sum1 <= sum2-target {
		return low - 1
	}
	return low
}

func calculateSum(arr []int, mid int) int {
	sum := 0
	for _, num := range arr {
		sum += min(num, mid)
	}
	return sum
}

func min(a int, b int) int {
	if a > b {
		return b
	}
	return a
}

```