1.题目

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

2.样例

1）示例 1：
输入：arr = [4,9,3], target = 10
输出：3
解释：当选择 value 为 3 时，数组会变成 [3, 3, 3]，和为 9 ，这是最接近 target 的方案。

2）示例 2：
输入：arr = [2,3,5], target = 10
输出：5

3）示例 3：
输入：arr = [60864,25176,27249,21296,20204], target = 56803
输出：11361

3.分析

1）感觉和之前做过的一道题很像，上来容易想当然就是认为最终答案就是数组中的值，但是这道题是abs，所以其实最终答案不一定就在数组中
2）考虑到最终ans的范围，可以将原始数组离散化成一维坐标，那么最终ans的取值有若干个空间：[1,arr[0]] , [arr[0], arr[1]]…[arr[i-1],arr[i]]之间，那么在每个区间中，目标函数也就是abs(sum-target)都是单调的，可以用二分，但是个人感觉这个数学公式太明显了，可以直接公式推出来二分的那么最终left和right

4.代码

class Solution {
public:int abs(int a,int b){return max(a-b,b-a);}vector<int> find_in_vec(vector<int>& arr, int target,vector<int>& sum){vector<int> ans1;int sum1=0,ans=abs(sum.back(),target),id=arr.back();for(int i=0;i<arr.size();i++){sum1=sum[i];sum1+=arr[i]*(arr.size()-i-1);sum1=abs(sum1,target);if(sum1<ans){ans=sum1;id=arr[i];}}ans1.push_back(ans);ans1.push_back(id);return ans1;}vector<int> get_sum(vector<int>& arr){vector<int> sum;for(int i=0;i<arr.size();i++){if(i==0) sum.push_back(arr[i]);else sum.push_back(sum.back()+arr[i]);}return sum;}vector<int> get_from_out(vector<int>& arr, int target,vector<int>& sum){vector<int> ans1;int ans=abs(sum.back(),target),id=arr.back(),sum1=0,sum2=0,left=0,right=0;for(int i=0;i<arr.size();i++){if(i==0) sum1=0,left=0;else sum1=sum[i-1],left=arr[i-1];right=arr[i];int id1=0;if(sum1>target) id1=left;else id1=abs(sum1,target)/(arr.size()-i);if(id1<left||id1>right) continue;sum2=abs(target,sum1+id1*(arr.size()-i));if(sum2<ans||(sum2==ans&&id1<id)){ans=sum2;id=id1;}id1++;sum2=abs(target,sum1+id1*(arr.size()-i));if(sum2<ans||(sum2==ans&&id1<id)){ans=sum2;id=id1;}}ans1.push_back(ans);ans1.push_back(id);return ans1;}int findBestValue(vector<int>& arr, int target) {sort(arr.begin(),arr.end());vector<int> sum=get_sum(arr);// vector<int> ans1=find_in_vec(arr,target,sum);vector<int> ans1=get_from_out(arr,target,sum);return ans1[1];}
};

5.思考

1）要注意边界的取值和特殊情况的考虑，容易WA
2）感觉目前的刷题节奏还是每天一随机，没有什么规律，考虑下一步刷题的方向吧。。