LeetCode 1300. 转变数组后最接近目标值的数组和 （排序+双重二分+前缀和）

转变数组后最接近目标值的数组和
由于选定一个数来转变数组之后产生的求和是具有单调性，所有可以二分解决，（这个过程有点像在实数域上二分求零点），然后考虑到每次求和可以用前缀和来优化，先用二分求出第一个大于这个值的下标，然后直接得出转变后的数组和。
时间复杂度：
$O(n*log(n)+log(C)*log(n))$,其中C是数组中的最大值。

class Solution {
public:int res = 1e9+10, ans = 1e5+10, n;vector<int> pre;int findBestValue(vector<int>& a, int target) {sort(a.begin(),a.end());n = a.size();pre = a;int l = 0, r = a[n-1];for(int i=1;i<n;i++){pre[i] += pre[i-1];}while(l<=r){int mid = l+(r-l)/2;int diff = getDifference(a,mid,target);if(diff<0){l = mid+1;}else{r = mid-1;}if(abs(diff)<res || abs(diff)==res && mid<ans){res = abs(diff);ans = mid;}}return ans;}int getDifference(vector<int>& a,int val,int target){int idx = upper_bound(a.begin(),a.end(),val)-a.begin();return (idx>0?pre[idx-1]:0)+val*(n-idx)-target;}
};