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

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);

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;
};