C++前缀和算法的应用:使数组相等的最小开销

简介: C++前缀和算法的应用:使数组相等的最小开销

本文涉及的基础知识点

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


目录
打赏
0
0
0
0
36
分享
相关文章
员工上网行为监控中的Go语言算法:布隆过滤器的应用
在信息化高速发展的时代,企业上网行为监管至关重要。布隆过滤器作为一种高效、节省空间的概率性数据结构,适用于大规模URL查询与匹配,是实现精准上网行为管理的理想选择。本文探讨了布隆过滤器的原理及其优缺点,并展示了如何使用Go语言实现该算法,以提升企业网络管理效率和安全性。尽管存在误报等局限性,但合理配置下,布隆过滤器为企业提供了经济有效的解决方案。
84 8
员工上网行为监控中的Go语言算法:布隆过滤器的应用
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
40 2
基于红黑树的局域网上网行为控制C++ 算法解析
在当今网络环境中,局域网上网行为控制对企业和学校至关重要。本文探讨了一种基于红黑树数据结构的高效算法,用于管理用户的上网行为,如IP地址、上网时长、访问网站类别和流量使用情况。通过红黑树的自平衡特性,确保了高效的查找、插入和删除操作。文中提供了C++代码示例,展示了如何实现该算法,并强调其在网络管理中的应用价值。
基于哈希表的文件共享平台 C++ 算法实现与分析
在数字化时代,文件共享平台不可或缺。本文探讨哈希表在文件共享中的应用,包括原理、优势及C++实现。哈希表通过键值对快速访问文件元数据(如文件名、大小、位置等),查找时间复杂度为O(1),显著提升查找速度和用户体验。代码示例展示了文件上传和搜索功能,实际应用中需解决哈希冲突、动态扩容和线程安全等问题,以优化性能。
探索企业文件管理软件:Python中的哈希表算法应用
企业文件管理软件依赖哈希表实现高效的数据管理和安全保障。哈希表通过键值映射,提供平均O(1)时间复杂度的快速访问,适用于海量文件处理。在Python中,字典类型基于哈希表实现,可用于管理文件元数据、缓存机制、版本控制及快速搜索等功能,极大提升工作效率和数据安全性。
65 0
C语言在机器学习中的应用及其重要性。C语言以其高效性、灵活性和可移植性,适合开发高性能的机器学习算法,尤其在底层算法实现、嵌入式系统和高性能计算中表现突出
本文探讨了C语言在机器学习中的应用及其重要性。C语言以其高效性、灵活性和可移植性,适合开发高性能的机器学习算法,尤其在底层算法实现、嵌入式系统和高性能计算中表现突出。文章还介绍了C语言在知名机器学习库中的作用,以及与Python等语言结合使用的案例,展望了其未来发展的挑战与机遇。
66 1
|
19天前
|
【C++面向对象——类与对象】Computer类(头歌实践教学平台习题)【合集】
声明一个简单的Computer类,含有数据成员芯片(cpu)、内存(ram)、光驱(cdrom)等等,以及两个公有成员函数run、stop。只能在类的内部访问。这是一种数据隐藏的机制,用于保护类的数据不被外部随意修改。根据提示,在右侧编辑器补充代码,平台会对你编写的代码进行测试。成员可以在派生类(继承该类的子类)中访问。成员,在类的外部不能直接访问。可以在类的外部直接访问。为了完成本关任务,你需要掌握。
61 19
【C++面向对象——类与对象】CPU类(头歌实践教学平台习题)【合集】
声明一个CPU类,包含等级(rank)、频率(frequency)、电压(voltage)等属性,以及两个公有成员函数run、stop。根据提示,在右侧编辑器补充代码,平台会对你编写的代码进行测试。​ 相关知识 类的声明和使用。 类的声明和对象的声明。 构造函数和析构函数的执行。 一、类的声明和使用 1.类的声明基础 在C++中,类是创建对象的蓝图。类的声明定义了类的成员,包括数据成员(变量)和成员函数(方法)。一个简单的类声明示例如下: classMyClass{ public: int
41 13
【C++面向对象——继承与派生】派生类的应用(头歌实践教学平台习题)【合集】
本实验旨在学习类的继承关系、不同继承方式下的访问控制及利用虚基类解决二义性问题。主要内容包括: 1. **类的继承关系基础概念**:介绍继承的定义及声明派生类的语法。 2. **不同继承方式下对基类成员的访问控制**:详细说明`public`、`private`和`protected`继承方式对基类成员的访问权限影响。 3. **利用虚基类解决二义性问题**:解释多继承中可能出现的二义性及其解决方案——虚基类。 实验任务要求从`people`类派生出`student`、`teacher`、`graduate`和`TA`类,添加特定属性并测试这些类的功能。最终通过创建教师和助教实例,验证代码
43 5
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等