题目描述：给你一个整数数组 arr 和一个目标值 target ，请你返回一个整数 value ，使得将数组中所有大于 value 的值变成 value 后，数组的和最接近 target （最接近表示两者之差的绝对值最小）。
如果有多种使得和最接近 target 的方案，请你返回这些整数中的最小值。
请注意，答案不一定是 arr 中的数字。
eg:
示例 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思路描述：首先题意就是把大于 value 的值缩小到 value，使得总和最接近 target。
最简单的做法就是先对整个数组排一下序，然后再求和 sum，如果 sum <= target，value 返回最大值就好了，因为没必要再缩小某些值了。
如果 sum > target，我们可以遍历一遍 arr，然后分别取 value 为数组中的值直到发现取第 i 个值 sum >= target，并且 i 左边的元素和为 sumLeft，那么如果 i 及 i 右边的数字全变成
ans = (target - sumLeft)/(n - i)，这时候总和就是 sumLeft + ans*(n - i) = target
但是因为 ans = (target - sumLeft)/(n - i) 是向下取整，所以要比较一下分别取 ans 和 ans+1哪个更接近 target。
比如：
1 2 3 target = 3，右边两个变成 (3 - 1)/2 = 1 最好
class Solution {
public:
int findBestValue(vector<int>& arr, int target) {
sort(arr.begin(), arr.end());//排序
int sum = accumulate(arr.begin(), arr.end(), 0);//求和
int n = arr.size();
if(sum <= target) return arr.back();
if(arr[0] * n >= target){
int ans = target/n;
if(target - ans * n < (ans + 1) * n - target)
return ans;
else
return ans + 1;
}
int sumLeft = arr[0];
for(int i = 1; i < n; i ++){
int sum = sumLeft + arr[i] * (n - i);
if(sum >= target){
int ans = (target - sumLeft)/(n - i);
if(target - sumLeft - ans*(n - i) <= (ans + 1) * (n - i) + sumLeft - target)
return ans;
else
return ans + 1;
break;
}
sumLeft += arr[i];
}
return 0;
}
};上一种思路可以优化的部分就是把遍历部分换成二分查找，实现起来也是一样的，就不详细写了。