LeetCode 1300. 转变数组后最接近目标值的数组和（二分查找）数据结构与算法Michael是个半路程序员-

1. 题目

给你一个整数数组 arr 和一个目标值 target ，请你返回一个整数 value ，
使得将数组中所有大于 value 的值变成 value 后，数组的和 最接近 target （最接近表示两者之差的绝对值最小）。

如果有多种使得和最接近 target 的方案，请你返回这些整数中的最小值。

请注意，答案不一定是 arr 中的数字。

示例 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   提示： 1 <= arr.length <= 10^4 1 <= arr[i], target <= 10^5 

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sum-of-mutated-array-closest-to-target
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

• 先将数组排序，求出前缀和
• 要找的这个数ans上下限 [0, arr_max]
• 如果这个数ans比0还小，数组所有的数将变成ans，target > 0，不会更接近
• 如果这个数ans比数组最大的还大，数组所有的数不变，跟target的差，也不变，但题目要求最小的ans，所以ans的范围是 [0, arr_max]
• 现在需要证明，数组的和与target的单调性：
  假设选取的数为 v2, a[i-1] <= v2 < a[i]
  此时，
  $a[0]+a[1]+…+a[i-1]+ v2+…+v2 (n-i个)-target-式1$

  a[0]+a[1]+...+a[i−1]+v2+...+v2(n−i个)−target−式1
  再次选择数 v1，a[i-1] <= v1 < v2
  此时，
  $a[0]+a[1]+…+a[i-1]+ v1+…+v1 (n-i个)-target – 式2$

  a[0]+a[1]+...+a[i−1]+v1+...+v1(n−i个)−target−式2
  上下做差：式1-式2 =
  $(v2-v1)*(n-i) >= 0$

  (v2−v1)∗(n−i)>=0
  选择数 v1，v1 < a[i-1] < v2
  此时，
  $a[0]+a[1]+…+a[i-2]+ v1+…+v1 (n-i+1个)-target – 式3$

  a[0]+a[1]+...+a[i−2]+v1+...+v1(n−i+1个)−target−式3
  上下做差：式1-式3 =
  $a[i-1]-v1+(v2-v1)*(n-i) >= 0$

  a[i−1]−v1+(v2−v1)∗(n−i)>=0
  所以上式是单调递增的！可以进行二分查找

class Solution { public: int findBestValue(vector<int>& arr, int target) { int i, l, r, mid, idx, diff, mindiff = INT_MAX, n = arr.size(), ans=INT_MAX; sort(arr.begin(),arr.end());      vector<int> presum(arr); for(i = 1; i < n; ++i)       presum[i] += presum[i-1];//前缀和      l = 0, r = arr[n-1];//范围 while(l <= r) {       mid = l+((r-l)>>1);       idx = binsearch(arr, mid);//二分查找mid这个值在数组中的位置       diff = (idx>0? presum[idx-1] : 0) +(n-idx)*mid-target; //函数式的值，函数单调递增 if(abs(diff) < mindiff) {        mindiff = abs(diff);        ans = mid;//有更小的 } else if((abs(diff) == mindiff))                 ans = min(ans,mid);//相等的情况下取更小的 if(diff < 0)//小了，要让他增大，在0左右寻找        l = mid+1; else if(diff > 0)        r = mid-1; else return ans; } return ans; } int binsearch(vector<int>& arr, int val) { //找第一个大于val的数的下标 int l = 0, r = arr.size()-1, mid; while(l <= r) {    mid = l+((r-l)>>1); if(arr[mid] > val) { if(mid==0 || arr[mid-1] <= val) return mid; else      r = mid-1; } else     l = mid+1; } return arr.size();//没找到，全部小于val } };