本文涉及的基础知识点
C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频
题目
给你两个下标从 0 开始的数组 nums 和 cost ，分别包含 n 个 正 整数。
你可以执行下面操作 任意 次：
将 nums 中 任意 元素增加或者减小 1 。
对第 i 个元素执行一次操作的开销是 cost[i] 。
请你返回使 nums 中所有元素 相等 的 最少 总开销。
示例 1：
输入：nums = [1,3,5,2], cost = [2,3,1,14]
输出：8
解释：我们可以执行以下操作使所有元素变为 2 ：
- 增加第 0 个元素 1 次，开销为 2 。
- 减小第 1 个元素 1 次，开销为 3 。
- 减小第 2 个元素 3 次，开销为 1 + 1 + 1 = 3 。
总开销为 2 + 3 + 3 = 8 。
这是最小开销。
示例 2：
输入：nums = [2,2,2,2,2], cost = [4,2,8,1,3]
输出：0
解释：数组中所有元素已经全部相等，不需要执行额外的操作。
参数范围：
n == nums.length == cost.length
1 <= n <= 105
1 <= nums[i], cost[i] <= 106
测试用例确保输出不超过 253-1。
分析
原理
假定最后所有数都变成x，那么x的取值范围是[min(nums),max(nums)]。如果x1<nin(nums)，那要先变成min(nums)，再继续变，显然x1的开销更大。
假定x为x1，开销为ll1，如果x为x1+1，那么开销会如何变化。
| 如果nums[i]小于x | 开销增加，比之前多增加1 |
| 如果nums[i]等于x | 开销增加，之前不变，现在加1 |
| 如果nums[i]等于x+1 | 开销减少，之前-1，现在不变 |
| 如果nums[i]大于x+1 | 开销减少，比之前少1 |
时间复杂度
分四步，每个时间复杂度都是O(n)，故总时间复杂度是O(n)。
步骤
| 一 | 求将各值加1，减少1的消耗，一个值可能有多个，也可能没有 |
| 二 | 求值小于j的所有数加1或减少1的消耗，也就是前缀和。 |
| 三 | 所有的数变成0的消耗 |
| 四 | 枚举x。 |
代码
核心代码
class Solution { public: long long minCost(vector& nums, vector& cost) { m_c = nums.size(); const int iMaxValue = *std::max_element(nums.begin(), nums.end()); vector vValueConst(iMaxValue+1);//vValueConst[j] 表示将所有nums[i]等于j 加或减1 的消耗 for (int i = 0; i < m_c; i++) { vValueConst[nums[i]] += cost[i]; } vector vSum = { 0 };//vValueConst[j] 表示将所有nums[i]<j 加或减1 的消耗 for (const auto& ll : vValueConst ) { vSum.emplace_back(ll + vSum.back()); } long long ll = 0;//记录将所有值变成x 的总消耗 for (int i = 0; i < m_c; i++) { ll += abs(nums[i] - 0LL) * cost[i]; } long long llRet = LLONG_MAX; for (int x = 0; x < iMaxValue; x++) { //[0,x+1) 消耗增加 ll += vSum[x + 1] - vSum[0]; //[x+1,…) ll -= vSum.back() - vSum[x+1]; llRet = min(llRet, ll); } return llRet; } int m_c; };
测试用例
int main() { Solution slu; vector nums, cost; long long res; nums = { 1, 3, 5, 2 }; cost = { 2, 3, 1, 14 }; res = slu.minCost(nums,cost); Assert(8LL ,res);
//CConsole::Out(res);
}
2023年3月旧代码
class Solution { public: long long minCost(vector& nums, vector& cost) { m_c = nums.size(); Init(nums,cost); return Cost(); } long long Cost() { long long llMin = (1000LL) * 1000 * 1000 * 1000 * 1000 * 1000; long long llLeftCost = 0, llRightCost = 0; for (int i = 1; i < m_c; i++) { llRightCost += abs((long long)m_vNums[i] - m_vNums[0])*m_vCost[i]; } llMin = min(llMin, llLeftCost+llRightCost);
for (int i = 1; i < m_c; i++) { llLeftCost += m_vSums[i]*(m_vNums[i] - m_vNums[i - 1]); llRightCost -= (m_vSums.back() - m_vSums[i ])*(m_vNums[i] - m_vNums[i - 1]); llMin = min(llMin, llLeftCost + llRightCost); } return llMin; } void Init(const vector<int>& nums,const vector<int>& cost) { std::multimap<int, int> m; for (int i = 0; i < m_c; i++) { m.emplace(nums[i], cost[i]); } for (const auto& it : m) { m_vNums.push_back(it.first); m_vCost.push_back(it.second); } m_vSums.push_back(0); for (const auto& n : m_vCost) { m_vSums.push_back(m_vSums.back() + n); } } int m_c; vector<int> m_vNums, m_vCost; vector<long long> m_vSums;
};
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法，请下载《闻缺陷则喜算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 充满正能量得对大家说
|
|-|
|闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。|
| 墨家名称的来源：有所得以墨记之。 |
|如果程序是一条龙，那算法就是他的是睛|
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境：
VS2022 C++17
