算法实例分析：使数组相等的最小开销

使数组相等的最小开销通过题意分析可知要让所有值相等必然不需要超出数据的最大最小值因此左右边界可以预先缩小范围。然后根据我们上面的分析不断缩小搜索边界范围。关于函数的计算只要统计所有数据与的差值再乘上权重即可。最后注意为了保证答案的正确性需要再在两端取一次最值class Solution { public: long long minCost(vectorint nums, vectorint cost) { auto sum [](int k) - long long { long long ans 0; for (int i 0; i nums.size(); i 1) { ans 1LL * cost[i] * abs(nums[i] - k); } return ans; }; int left *min_element(nums.begin(), nums.end()); int right *max_element(nums.begin(), nums.end()); while (left right) { int lmid left (right - left) / 3; int rmid right - (right - left) / 3; /// 凹区间 if (sum(lmid) sum(rmid)) { right rmid - 1; } else { left lmid 1; } } // 最终取两点间的最值 return min(sum(left), sum(right)); } };总结再回头看一下二分与三分的书写形式会发现两者是如此的相像。因此我们要着重注意两者的区别本文只是列举了两个典型的简单例子各种应用场景对算法的具体细节有所差异。但是万变不离其宗只要理清搜索的实际的搜索流程就不需要僵硬地套用所谓的模板。