C++前缀和算法的应用:从仓库到码头运输箱子原理、源码、测试用例

简介: C++前缀和算法的应用:从仓库到码头运输箱子原理、源码、测试用例

本文涉及的基础知识点

C++算法:前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频

双指针

单调双向队列

题目

你有一辆货运卡车,你需要用这一辆车把一些箱子从仓库运送到码头。这辆卡车每次运输有 箱子数目的限制 和 总重量的限制 。

给你一个箱子数组 boxes 和三个整数 portsCount, maxBoxes 和 maxWeight ,其中 boxes[i] = [portsi, weighti] 。

portsi 表示第 i 个箱子需要送达的码头, weightsi 是第 i 个箱子的重量。

portsCount 是码头的数目。

maxBoxes 和 maxWeight 分别是卡车每趟运输箱子数目和重量的限制。

箱子需要按照 数组顺序 运输,同时每次运输需要遵循以下步骤:

卡车从 boxes 队列中按顺序取出若干个箱子,但不能违反 maxBoxes 和 maxWeight 限制。

对于在卡车上的箱子,我们需要 按顺序 处理它们,卡车会通过 一趟行程 将最前面的箱子送到目的地码头并卸货。如果卡车已经在对应的码头,那么不需要 额外行程 ,箱子也会立马被卸货。

卡车上所有箱子都被卸货后,卡车需要 一趟行程 回到仓库,从箱子队列里再取出一些箱子。

卡车在将所有箱子运输并卸货后,最后必须回到仓库。

请你返回将所有箱子送到相应码头的 最少行程 次数。

示例 1:

输入:boxes = [[1,1],[2,1],[1,1]], portsCount = 2, maxBoxes = 3, maxWeight = 3

输出:4

解释:最优策略如下:

  • 卡车将所有箱子装上车,到达码头 1 ,然后去码头 2 ,然后再回到码头 1 ,最后回到仓库,总共需要 4 趟行程。
    所以总行程数为 4 。
    注意到第一个和第三个箱子不能同时被卸货,因为箱子需要按顺序处理(也就是第二个箱子需要先被送到码头 2 ,然后才能处理第三个箱子)。
    示例 2:
    输入:boxes = [[1,2],[3,3],[3,1],[3,1],[2,4]], portsCount = 3, maxBoxes = 3, maxWeight = 6
    输出:6
    解释:最优策略如下:
  • 卡车首先运输第一个箱子,到达码头 1 ,然后回到仓库,总共 2 趟行程。
  • 卡车运输第二、第三、第四个箱子,到达码头 3 ,然后回到仓库,总共 2 趟行程。
  • 卡车运输第五个箱子,到达码头 2 ,回到仓库,总共 2 趟行程。
    总行程数为 2 + 2 + 2 = 6 。
    示例 3:
    输入:boxes = [[1,4],[1,2],[2,1],[2,1],[3,2],[3,4]], portsCount = 3, maxBoxes = 6, maxWeight = 7
    输出:6
    解释:最优策略如下:
  • 卡车运输第一和第二个箱子,到达码头 1 ,然后回到仓库,总共 2 趟行程。
  • 卡车运输第三和第四个箱子,到达码头 2 ,然后回到仓库,总共 2 趟行程。
  • 卡车运输第五和第六个箱子,到达码头 3 ,然后回到仓库,总共 2 趟行程。
    总行程数为 2 + 2 + 2 = 6 。
    示例 4:
    输入:boxes = [[2,4],[2,5],[3,1],[3,2],[3,7],[3,1],[4,4],[1,3],[5,2]], portsCount = 5, maxBoxes = 5, maxWeight = 7
    输出:14
    解释:最优策略如下:
  • 卡车运输第一个箱子,到达码头 2 ,然后回到仓库,总共 2 趟行程。
  • 卡车运输第二个箱子,到达码头 2 ,然后回到仓库,总共 2 趟行程。
  • 卡车运输第三和第四个箱子,到达码头 3 ,然后回到仓库,总共 2 趟行程。
  • 卡车运输第五个箱子,到达码头 3 ,然后回到仓库,总共 2 趟行程。
  • 卡车运输第六和第七个箱子,到达码头 3 ,然后去码头 4 ,然后回到仓库,总共 3 趟行程。
  • 卡车运输第八和第九个箱子,到达码头 1 ,然后去码头 5 ,然后回到仓库,总共 3 趟行程。
    总行程数为 2 + 2 + 2 + 2 + 3 + 3 = 14 。

提示:

1 <= boxes.length <= 105

1 <= portsCount, maxBoxes, maxWeight <= 105

1 <= portsi <= portsCount

1 <= weightsi <= maxWeight

可理解行强的解法

如果有多种运输的boxs[0,i)的方式,只需要保留行程最少的方式,且只需要记录最小行程,此值用m_vRet[i]记录。分成两步:第一步,运输box[0,j),第二步运输[j,i)。一次可以运输完成,可以看成第一步是box[0,0)。枚举i,j的时间复杂度都是O(n),总时间复杂度是O(n*n)。

利用前缀和计算[j,i)的箱子总重量

vWeightSum[i],记录了boxs[0,i)的重中立,vWeightSum[i]-vWeightSum[j]。

利用前缀和计算[i,j)需要单独下车的次数

vDownSum[i]记录[0,i)需要单独下车的次数。vDown[j]-vDownSum[i]。和前面的箱子不同,则需要单独下车。

优化枚举

m_vRet[i] = min(…,X) X=m_vRet[j]+1 + 1 + vDown[j+1,i)。 1+1 表示返程和下第一箱子,从第二个箱子起要计算要单独下。X = m_vRet[j]+1+1+vDown[i] - vDown[j+1] ,令 Y= m_vRet[j]-vDow[j+1],则X=Y + 2 + vDown[i] ,显然Y可以提前计算。每次处理完i,将Y记录到setPre中。setPre对应的索引为[left,i),如果[left,i)超量或超重,则left++,并更新setPre。

时间复杂度

枚举i,时间复杂度。二分查找setPre,时间复杂度O(logn),总时间复杂度O(nlogn)。

核心代码

class Solution {
public:
int boxDelivering(vector<vector>& boxes, int portsCount, int maxBoxes, int maxWeight) {
m_c = boxes.size();
m_vRet.resize(m_c+1);//记录boxes[0,i) 需的最小行程数
vector vWeightSum = { 0 };//箱子重量前缀和
for (const auto& v : boxes)
{
vWeightSum.emplace_back(v[1] + vWeightSum.back());
}
vector vDownSum = { 0,0 };//假定不是本车的第一个箱子,卸货需要的次数
for (int i = 1; i < m_c; i++)
{
vDownSum.emplace_back(vDownSum.back() + (boxes[i][0] != boxes[i-1][0]));
}
std::multiset setPre = { 0 }; //记录可以作为前一趟的最小行程数-vDownSum[i + 1]
int left = 0;//[left,i)是上一趟的行程
for (int i = 1; i <= m_c; i++)
{
// [left,i)为空,不会超重,也不会超量。所以无需判断是否为空
while ((i - left > maxBoxes) || (vWeightSum[i] - vWeightSum[left] > maxWeight))
{
//如果[left,i)超重或超亮
const int tmp = m_vRet[left ] - vDownSum[left+1 ];
setPre.erase(setPre.find(tmp));
left++;
}
m_vRet[i ] = *setPre.begin() + 2 + vDownSum[i] ;
if (i + 1 <= m_c)
{
setPre.emplace(m_vRet[i] - vDownSum[i + 1]);
}
}
return m_vRet.back();
}
int m_c;
vector m_vRet;
};

测试用例

template
void Assert(const vector& v1, const vector& v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
assert(v1[i] == v2[i]);
}
}
template
void Assert(const T& t1, const T& t2)
{
assert(t1 == t2);
}
int main()
{
vector<vector> boxes = { {1,1},{2,1},{1,1} };
int portsCount = 2, maxBoxes = 3, maxWeight = 3;
auto res = Solution().boxDelivering(boxes, portsCount, maxBoxes, maxWeight);
Assert(4, res);
boxes = { {1,2},{3,3},{3,1},{3,1},{2,4} };
portsCount = 3, maxBoxes = 3, maxWeight =6;
res = Solution().boxDelivering(boxes, portsCount, maxBoxes, maxWeight);
Assert(6, res);
boxes = { {2,4},{2,5},{3,1},{3,2},{3,7},{3,1},{4,4},{1,3},{5,2} };
portsCount = 5, maxBoxes = 5, maxWeight = 7;
res = Solution().boxDelivering(boxes, portsCount, maxBoxes, maxWeight);
Assert(14, res);
//CConsole::Out(res);

}

优化二:单调双向队列

原理

setPre的旧值如果大于等于新值,则被淘汰了。这意味着值是按升序排序的。移除值有两种原因:一,旧值比新值大,被淘汰。从容器尾淘汰。二,旧值超重或超过数量了,从容器头淘汰。所以用双向队列。

代码

class Solution {
public:
int boxDelivering(vector<vector>& boxes, int portsCount, int maxBoxes, int maxWeight) {
m_c = boxes.size();
m_vRet.resize(m_c+1);//记录boxes[0,i) 需的最小行程数
vector vWeightSum = { 0 };//箱子重量前缀和
for (const auto& v : boxes)
{
vWeightSum.emplace_back(v[1] + vWeightSum.back());
}
vector vDownSum = { 0,0 };//假定不是本车的第一个箱子,卸货需要的次数
for (int i = 1; i < m_c; i++)
{
vDownSum.emplace_back(vDownSum.back() + (boxes[i][0] != boxes[i-1][0]));
}
std::deque<pair<int, int>> mSumJ = { { 0,0} };
for (int i = 1; i <= m_c; i++)
{
// [left,i)为空,不会超重,也不会超量。所以无需判断是否为空
while (mSumJ.size() &&((i - mSumJ.front().second > maxBoxes) || (vWeightSum[i] - vWeightSum[mSumJ.front().second] > maxWeight)))
{
//如果[left,i)超重或超亮
mSumJ.pop_front();
}
m_vRet[i ] = mSumJ.front().first + 2 + vDownSum[i] ;
if (i + 1 > m_c)
{
continue;
}
const int iNew = m_vRet[i] - vDownSum[i + 1];
while (mSumJ.size() && (mSumJ.back().first >= iNew))
{
mSumJ.pop_back();
}
mSumJ.emplace_back(iNew, i);
}
return m_vRet.back();
}
int m_c;
vector m_vRet;
};

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步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
分享
相关文章
基于 C++ 语言的迪杰斯特拉算法在局域网计算机管理中的应用剖析
在局域网计算机管理中,迪杰斯特拉算法用于优化网络路径、分配资源和定位故障节点,确保高效稳定的网络环境。该算法通过计算最短路径,提升数据传输速率与稳定性,实现负载均衡并快速排除故障。C++代码示例展示了其在网络模拟中的应用,为企业信息化建设提供有力支持。
42 15
短视频到底如何推荐的?深度剖析视频算法推送原理详细且专业的解读-优雅草卓伊凡-【01】短视频算法推荐之数据收集
短视频到底如何推荐的?深度剖析视频算法推送原理详细且专业的解读-优雅草卓伊凡-【01】短视频算法推荐之数据收集
45 12
短视频到底如何推荐的?深度剖析视频算法推送原理详细且专业的解读-优雅草卓伊凡-【01】短视频算法推荐之数据收集
|
10天前
|
MBTI十六型人格职业性格测试源码完整版
MBTI十六型人格职业性格测试源码完整版
45 11
「ximagine」业余爱好者的非专业显示器测试流程规范,同时也是本账号输出内容的数据来源!如何测试显示器?荒岛整理总结出多种测试方法和注意事项,以及粗浅的原理解析!
本期内容为「ximagine」频道《显示器测试流程》的规范及标准,我们主要使用Calman、DisplayCAL、i1Profiler等软件及CA410、Spyder X、i1Pro 2等设备,是我们目前制作内容数据的重要来源,我们深知所做的仍是比较表面的活儿,和工程师、科研人员相比有着不小的差距,测试并不复杂,但是相当繁琐,收集整理测试无不花费大量时间精力,内容不完善或者有错误的地方,希望大佬指出我们好改进!
108 16
「ximagine」业余爱好者的非专业显示器测试流程规范,同时也是本账号输出内容的数据来源!如何测试显示器?荒岛整理总结出多种测试方法和注意事项,以及粗浅的原理解析!
JS数组操作方法全景图,全网最全构建完整知识网络!js数组操作方法全集(实现筛选转换、随机排序洗牌算法、复杂数据处理统计等情景详解,附大量源码和易错点解析)
这些方法提供了对数组的全面操作,包括搜索、遍历、转换和聚合等。通过分为原地操作方法、非原地操作方法和其他方法便于您理解和记忆,并熟悉他们各自的使用方法与使用范围。详细的案例与进阶使用,方便您理解数组操作的底层原理。链式调用的几个案例,让您玩转数组操作。 只有锻炼思维才能可持续地解决问题,只有思维才是真正值得学习和分享的核心要素。如果这篇博客能给您带来一点帮助,麻烦您点个赞支持一下,还可以收藏起来以备不时之需,有疑问和错误欢迎在评论区指出~
从集思录可转债数据探秘:Python与C++实现的移动平均算法应用
本文探讨了如何利用移动平均算法分析集思录提供的可转债数据,帮助投资者把握价格趋势。通过Python和C++两种编程语言实现简单移动平均(SMA),展示了数据处理的具体方法。Python代码借助`pandas`库轻松计算5日SMA,而C++代码则通过高效的数据处理展示了SMA的计算过程。集思录平台提供了详尽且及时的可转债数据,助力投资者结合算法与社区讨论,做出更明智的投资决策。掌握这些工具和技术,有助于在复杂多变的金融市场中挖掘更多价值。
56 12
|
22天前
|
【📕分布式锁通关指南 04】redis分布式锁的细节问题以及RedLock算法原理
本文深入探讨了基于Redis实现分布式锁时遇到的细节问题及解决方案。首先,针对锁续期问题,提出了通过独立服务、获取锁进程自己续期和异步线程三种方式,并详细介绍了如何利用Lua脚本和守护线程实现自动续期。接着,解决了锁阻塞问题,引入了带超时时间的`tryLock`机制,确保在高并发场景下不会无限等待锁。最后,作为知识扩展,讲解了RedLock算法原理及其在实际业务中的局限性。文章强调,在并发量不高的场景中手写分布式锁可行,但推荐使用更成熟的Redisson框架来实现分布式锁,以保证系统的稳定性和可靠性。
41 0
【📕分布式锁通关指南 04】redis分布式锁的细节问题以及RedLock算法原理
基于SpringBoot+Vue实现的大学生体质测试管理系统设计与实现(系统源码+文档+数据库+部署)
面向大学生毕业选题、开题、任务书、程序设计开发、论文辅导提供一站式服务。主要服务:程序设计开发、代码修改、成品部署、支持定制、论文辅导,助力毕设!
【C++面向对象——继承与派生】派生类的应用(头歌实践教学平台习题)【合集】
本实验旨在学习类的继承关系、不同继承方式下的访问控制及利用虚基类解决二义性问题。主要内容包括: 1. **类的继承关系基础概念**:介绍继承的定义及声明派生类的语法。 2. **不同继承方式下对基类成员的访问控制**:详细说明`public`、`private`和`protected`继承方式对基类成员的访问权限影响。 3. **利用虚基类解决二义性问题**:解释多继承中可能出现的二义性及其解决方案——虚基类。 实验任务要求从`people`类派生出`student`、`teacher`、`graduate`和`TA`类,添加特定属性并测试这些类的功能。最终通过创建教师和助教实例,验证代码
71 5

热门文章

最新文章

AI助理

你好,我是AI助理

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