【C++二分查找决策包容性】1300. 转变数组后最接近目标值的数组和

本文涉及的基础知识点

C++二分查找
决策包容性

LeetCode1300. 转变数组后最接近目标值的数组和

给你一个整数数组 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⁴
1 <= arr[i], target <= 10⁵

方法一：

排序，然后枚举arr[i]修改，arr[i+1]不修改。时间复杂度的瓶颈在排序，时间复杂度：O(nlogn)。

方法二：

最终结果res一定在[1,10⁵],下面用决策包容性来证明。如果res>=10⁵，任何数都不会改变，都是原数组。故同样接近target，同样接近取最小值10⁵。
如果res <= 0，新数组之和，一定小于target。故0最接近。
令Cal(value)计算新数组之和。
本题 $\iff$ Cal(res) >= target，res最小。比较Check(res)和Check(res-1)谁接近target
二分类型：寻找首端。
参数范围：[1,10⁵]
Check函数：return Cal(mid) >= target。时间复杂度：O(n)，总时间复杂度：O(nlogn)。
特殊处理：Check函数全部为false，返回arr的最大值。

代码

核心代码

template<class INDEX_TYPE>
class CBinarySearch
{
public:CBinarySearch(INDEX_TYPE iMinIndex, INDEX_TYPE iMaxIndex):m_iMin(iMinIndex),m_iMax(iMaxIndex) {}template<class _Pr>INDEX_TYPE FindFrist( _Pr pr){auto left = m_iMin - 1;auto rightInclue = m_iMax;while (rightInclue - left > 1){const auto mid = left + (rightInclue - left) / 2;if (pr(mid)){rightInclue = mid;}else{left = mid;}}return rightInclue;}template<class _Pr>INDEX_TYPE FindEnd( _Pr pr){int leftInclude = m_iMin;int right = m_iMax + 1;while (right - leftInclude > 1){const auto mid = leftInclude + (right - leftInclude) / 2;if (pr(mid)){leftInclude = mid;}else{right = mid;}}return leftInclude;}
protected:const INDEX_TYPE m_iMin, m_iMax;
};class Solution {public:int findBestValue(vector<int>& arr, int target) {auto Cal = [&](int val) {int sum = 0;for (const auto& n : arr) {sum += n - max(0, n - val);}return sum ;};auto res = CBinarySearch(0, 100'000).FindFrist([&](int mid) {return Cal(mid) >= target; });if (Cal(res) < target) {return *std::max_element(arr.begin(),arr.end());}return abs(target - Cal(res)) < abs(target - Cal(res - 1)) ? res : res - 1;}};

单元测试

vector<int> arr;int target;TEST_METHOD(TestMethod11){arr = { 4,9,3 }, target = 10;auto res = Solution().findBestValue(arr, target);AssertEx(3, res);}TEST_METHOD(TestMethod12){arr = { 2,3,5 }, target = 10;auto res = Solution().findBestValue(arr, target);AssertEx(5, res);}TEST_METHOD(TestMethod13){arr = { 60864,25176,27249,21296,20204 }, target = 56803;auto res = Solution().findBestValue(arr, target);AssertEx(11361, res);}TEST_METHOD(TestMethod14){arr = { 2,3,5 }, target = 11;auto res = Solution().findBestValue(arr, target);AssertEx(5, res);}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功