題目描述：
給你一個整數陣列 arr 和一個目標值 target ，請你回傳一個整數 value ，使得將陣列中所有大于 value 的值變成 value 后，陣列的和最接近 target （最接近表示兩者之差的絕對值最小），
如果有多種使得和最接近 target 的方案，請你回傳這些整數中的最小值，
請注意，答案不一定是 arr 中的數字，
提示中給的是二分法，而二分法官方解答已經很詳細了，下面是我的解體思路
首先，這道題的根本目的是在陣列中切一刀，那么具體在哪切一刀呢？
根據題意我們可以確定value的最小值是1，最大值可以取到arr陣列的最大值，那么最暴力的方法當然是直接再value的取值范圍里采用回圈遍歷，找出value的值，當然，這樣做的時間成本太大了，力扣是不會給你分的（我已經試過了），
為了清晰的描述我的思路，這里先舉個栗子，
為了方便，我這里直接給出一個已經排列好的陣列，（陣列的排列可以直接使用sort()函式）
arr[]={7,9,12,17,19,25} target=80
這里的陣列大小是6，要讓它的和接近80，那么也就是說這6個數的平均值要接近13.33（80/6),也就是說，此陣列不可能在12的前面切一刀
若在12后面17前面切一刀，新陣列arr[7,9,12,x,x,x]，為了使陣列和更接近target：
那么 80-7-9-12=52 x=52/3=17.33<17.5，
所以X最合適的值就是17，即value=https://www.cnblogs.com/pearli/p/17
代碼如下：
class Solution { public: int findBestValue(vector<int>& arr, int target) { sort(arr.begin(),arr.end()); //將陣列從小到大排列 int pre=0,rest=arr.size(); //將陣列切成兩段 pre表示前一段數字的和，rest表述后一段數字的個數 double temp; //存盤平均數x的值 for(int i=0;i<arr.size();i++){ temp = double(target-pre)/rest; //回圈遍歷 if(temp<=arr[i]){ if(temp-int(temp)>0.5) return int(temp)+1; //若是平均值小于陣列內的最小值，那么value就等于四舍五入后的平均值 return int(temp); } pre+=arr[i]; rest--; } return arr[arr.size()-1]; //若是平均值大于陣列內的最大值，那么value就等于陣列內的最大值 } };如果有什么問題，歡迎大家指正！
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/13768.html
標籤：C++
下一篇：C++ 靜態資料成員