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

2023-10-21 16:44
文章标签 算法 c++ 源码 应用 原理 仓库 箱子 运输 前缀 测试用例 码头

本文主要是介绍C++前缀和算法的应用：从仓库到码头运输箱子原理、源码、测试用例，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

本文涉及的基础知识点

C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频
双指针
单调双向队列

题目

你有一辆货运卡车，你需要用这一辆车把一些箱子从仓库运送到码头。这辆卡车每次运输有 箱子数目的限制 和 总重量的限制 。
给你一个箱子数组 boxes 和三个整数 portsCount, maxBoxes 和 maxWeight ，其中 boxes[i] = [ports​​i​, weighti] 。
ports​​i 表示第 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 <= ports​​i <= 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

这篇关于C++前缀和算法的应用：从仓库到码头运输箱子原理、源码、测试用例的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

原文地址:
http://www.chinasem.cn/article/255665。

相关文章

Go 语言中的select语句详解及工作原理

Go 语言中的select语句详解及工作原理

《Go语言中的select语句详解及工作原理》在Go语言中,select语句是用于处理多个通道（channel）操作的一种控制结构,它类似于switch语句,本文给大家介绍Go语言中的select语... 目录Go 语言中的 select 是做什么的基本功能语法工作原理示例示例 1：监听多个通道示例 2：带
阅读更多...
如何高效移除C++关联容器中的元素

如何高效移除C++关联容器中的元素

《如何高效移除C++关联容器中的元素》关联容器和顺序容器有着很大不同,关联容器中的元素是按照关键字来保存和访问的,而顺序容器中的元素是按它们在容器中的位置来顺序保存和访问的,本文介绍了如何高效移除C+... 目录一、简介二、移除给定位置的元素三、移除与特定键值等价的元素四、移除满足特android定条件的元
阅读更多...
鸿蒙中@State的原理使用详解(HarmonyOS 5)

鸿蒙中@State的原理使用详解(HarmonyOS 5)

《鸿蒙中@State的原理使用详解(HarmonyOS5)》@State是HarmonyOSArkTS框架中用于管理组件状态的核心装饰器,其核心作用是实现数据驱动UI的响应式编程模式,本文给大家介绍... 目录一、@State在鸿蒙中是做什么的？二、@Spythontate的基本原理1. 依赖关系的收集2.
阅读更多...
Python获取C++中返回的char*字段的两种思路

Python获取C++中返回的char*字段的两种思路

《Python获取C++中返回的char*字段的两种思路》有时候需要获取C++函数中返回来的不定长的char*字符串,本文小编为大家找到了两种解决问题的思路,感兴趣的小伙伴可以跟随小编一起学习一下... 有时候需要获取C++函数中返回来的不定长的char*字符串，目前我找到两种解决问题的思路，具体实现如下：
阅读更多...
C++ Sort函数使用场景分析

C++ Sort函数使用场景分析

《C++Sort函数使用场景分析》sort函数是algorithm库下的一个函数,sort函数是不稳定的,即大小相同的元素在排序后相对顺序可能发生改变,如果某些场景需要保持相同元素间的相对顺序,可使... 目录C++ Sort函数详解一、sort函数调用的两种方式二、sort函数使用场景三、sort函数排序
阅读更多...
C语言函数递归实际应用举例详解

C语言函数递归实际应用举例详解

《C语言函数递归实际应用举例详解》程序调用自身的编程技巧称为递归,递归做为一种算法在程序设计语言中广泛应用,：本文主要介绍C语言函数递归实际应用举例的相关资料,文中通过代码介绍的非常详细,需要的朋... 目录前言一、递归的概念与思想二、递归的限制条件 三、递归的实际应用举例（一）求 n 的阶乘（二）顺序打印
阅读更多...
Java调用C++动态库超详细步骤讲解(附源码)

Java调用C++动态库超详细步骤讲解(附源码)

《Java调用C++动态库超详细步骤讲解(附源码)》C语言因其高效和接近硬件的特性,时常会被用在性能要求较高或者需要直接操作硬件的场合,：本文主要介绍Java调用C++动态库的相关资料,文中通过代... 目录一、直接调用C++库第一步：动态库生成（vs2017+qt5.12.10）第二步：Java调用C++
阅读更多...
springboot+dubbo实现时间轮算法

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n
阅读更多...
C/C++错误信息处理的常见方法及函数

C/C++错误信息处理的常见方法及函数

《C/C++错误信息处理的常见方法及函数》C/C++是两种广泛使用的编程语言,特别是在系统编程、嵌入式开发以及高性能计算领域,：本文主要介绍C/C++错误信息处理的常见方法及函数,文中通过代码介绍... 目录前言1. errno 和 perror()示例：2. strerror()示例：3. perror(
阅读更多...
C++变换迭代器使用方法小结

C++变换迭代器使用方法小结

《C++变换迭代器使用方法小结》本文主要介绍了C++变换迭代器使用方法小结,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录1、源码2、代码解析代码解析：transform_iterator1. transform_iterat
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2