题意
给定一个数组，从中选取一个数字a,下标index，数组的长度len，使得。abs((n-index+1)*a + suma -target)值最小。具体来说，比a 小的数字之和suma + 比a大的数字(变成a)之和 + a 能够接近target的值。
解体方法
一种时采用排序的方法，将数组进行排序，找到这个数字的下标i 使得target - (nums[0]+...+nums[i]) < nums[i]*(nums.size()-i) ，然后将剩余的和(target-(nums[0]+...+nums[i]))/(nums.size()-i)
一种采用二分的方法进行。low=0, high=target,mid=(low+high)/2,如果diff(mid)<diff(mid+1)说明这个数字大了，说明要减小，反之说明这个数字小了要增大。
diff(mid) 描述的时 arr中比mid小的数字之和 suma 和?mid*(nums.size()-i)的和与target的数值之间的距离。?
代码
排序
class Solution {
public:
int findBestValue(vector<int>& arr, int target) {
sort(arr.begin(), arr.end());
int i=0, lens = arr.size()-1;
while(i<=lens && target>arr[i]*(lens-i+1)){ //lens-i+1 因为如果i=lens时，
target -= arr[i];
i++;
}
return (i==lens+1)?arr[lens]:int(round((target-0.0001)/(lens+1-i)));
}
};二分
class Solution {
public:
int diff(vector<int> arr, int target, int mid){
int sum=0;
for(auto a:arr){
sum += min(a, mid);
}
return abs(target-sum);
}
int findBestValue(vector<int>& arr, int target) {
int high=target, low=0, mid;
while(low<high){
mid = low + (high-low)/2;
if(diff(arr, target, mid) <= diff(arr, target, mid+1)){
high=mid;
}else{
low = mid+1;
}
}
return low;
}
};
