【线段树】【前缀和】：1687从仓库到码头运输箱子-阿里云开发者社区

本题简单解法

C++前缀和算法的应用：1687从仓库到码头运输箱子

本文涉及的基础知识点

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

线段树

LeetCode1687从仓库到码头运输箱子

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

给你一个箱子数组 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

线段树

lineTree[j]表示最后一趟运输boxs[j…i-1]的最小行程数，不包括返回

boxs[left…i]可以同车而不超重,如果有多个left，取最小值。

lineTree[i] = min ⁡ x : l e f t i − 1 + 1 + 1 \min_{x:left}^{i-1}+1+1minx:lefti−1+1+1

lineTree[0…left-1]不会被使用，所以无需维护。当i++时 lineTree[j]的含义从最后一趟运输 boxs[j…i-1]变成最后一趟运行boxs[j…i]。

如果boxs[i][0]!=boxs[i-1][0]，lineTree[left…i-1] 全部+1。

最后结果：[left…n-1]的最小值。

本题解用到了线段树的区间更新、区间查询。

代码

核心代码

template<class TSave, class TRecord>
class CLineTree
{
public:
  CLineTree(int iEleSize, TRecord recordNull=0)
    :m_iEleSize(iEleSize), m_vArr(m_iEleSize * 4), m_vRecord(m_iEleSize * 4, recordNull), m_recordNull(recordNull)
  {
  }
  void Update(int iLeftIndex, int iRightIndex, TRecord value)
  {
    Update(1, 1, m_iEleSize, iLeftIndex + 1, iRightIndex + 1, value);
  }
  void Query( int iLeftIndex, int iRightIndex)
  {
    Query( 1, 1, m_iEleSize, iLeftIndex + 1, iRightIndex + 1);
  }
private:
  virtual void OnQuery(TSave& save) = 0;
  virtual void OnUpdateRecord(TRecord& old, const TRecord& newRecord) = 0;
  virtual void OnUpdateParent(TSave& par, const TSave& left, const TSave& r) = 0;
  virtual void OnUpdate(TSave& save, const int& len, const TRecord& update) = 0;
  void Query( int iNode, int iSaveLeft, int iSaveRight, int iQueryLeft, int iQueryRight)
  {
    if ((iQueryLeft <= iSaveLeft) && (iQueryRight >= iSaveRight))
    {
      OnQuery(m_vArr[iNode]);
      return;
    }
    Fresh(iNode, iSaveLeft, iSaveRight);
    const int iMid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
    if (iMid >= iQueryLeft)
    {
      Query( iNode * 2, iSaveLeft, iMid, iQueryLeft, iQueryRight);
    }
    if (iMid + 1 <= iQueryRight)
    {
      Query( iNode * 2 + 1, iMid + 1, iSaveRight, iQueryLeft, iQueryRight);
    }
  }
  void Update(int iNode, int iSaveLeft, int iSaveRight, int iOpeLeft, int iOpeRight, TRecord value)
  {
    if (iNode >= m_vArr.size())
    {
      return;
    }
    if ((iOpeLeft <= iSaveLeft) && (iOpeRight >= iSaveRight))
    {
      OnUpdate(m_vArr[iNode], min(iSaveRight, iOpeRight) - max(iSaveLeft, iOpeLeft) + 1, value);
      OnUpdateRecord(m_vRecord[iNode], value);
      return;
    }
    Fresh(iNode, iSaveLeft, iSaveRight);
    const int iMid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
    if (iMid >= iOpeLeft)
    {
      Update(iNode * 2, iSaveLeft, iMid, iOpeLeft, iOpeRight, value);
    }
    if (iMid + 1 <= iOpeRight)
    {
      Update(iNode * 2 + 1, iMid + 1, iSaveRight, iOpeLeft, iOpeRight, value);
    }
    // 如果有后代，至少两个后代
    OnUpdateParent(m_vArr[iNode], m_vArr[iNode * 2], m_vArr[iNode * 2 + 1]);
  }
  void Fresh(int iNode, int iDataLeft, int iDataRight)
  {
    if (m_recordNull == m_vRecord[iNode])
    {
      return;
    }
    const int iMid = iDataLeft + (iDataRight - iDataLeft) / 2;
    Update(iNode * 2, iDataLeft, iMid, iDataLeft, iMid, m_vRecord[iNode]);
    Update(iNode * 2 + 1, iMid + 1, iDataRight, iMid + 1, iDataRight, m_vRecord[iNode]);
    m_vRecord[iNode] = m_recordNull;
  }
  const int m_iEleSize;
  vector<TSave> m_vArr;
  vector<TRecord> m_vRecord;
  const TRecord m_recordNull;
};
template<class TSave = int , class TRecord = int>
class CMinLineTree : public CLineTree<TSave, TRecord>
{
public:
  using CLineTree<TSave, TRecord>::CLineTree;
  int m_iQueryValue = INT_MAX;
protected:
  virtual void OnQuery(TSave& save) override
  {
    m_iQueryValue = min(m_iQueryValue, save);
  }
  virtual void OnUpdateRecord(TRecord& old, const TRecord& newRecord) override
  {
    old += newRecord;
  }
  virtual void OnUpdateParent(TSave& par, const TSave& left, const TSave& r) override
  {
    par = min(left, r);
  }
  virtual void OnUpdate(TSave& save, const int& len, const TRecord& update) override
  {
    save += update;
  }
  
};
 
  class Solution {
  public:
    int boxDelivering(vector<vector<int>>& boxes, int portsCount, int maxBoxes, int maxWeight) {
      m_c = boxes.size();
      
      vector<long long> vWeightSum = { 0 };//箱子重量前缀和
      for (const auto& v : boxes)
      {
        vWeightSum.emplace_back(v[1] + vWeightSum.back());
      }
      CMinLineTree<> lineTree(m_c);//lineTree[j]表示最后一趟运输boxs[i...j-1]的最小行程数，不包括返回
      lineTree.Update(0, 0, 1);
      int left = 0;
      for (int i = 1; i < m_c; i++)
      {
        lineTree.m_iQueryValue = INT_MAX / 10;
        lineTree.Query(left, i - 1);
        lineTree.Update(i, i, lineTree.m_iQueryValue + 2);
        for (; (i - left + 1 > maxBoxes) || (vWeightSum[i + 1] - vWeightSum[left] > maxWeight); left++);
        if ((boxes[i][0] != boxes[i - 1][0])&&( left <= i-1))
        {
          lineTree.Update(left, i - 1, 1);
        }
      }
      lineTree.m_iQueryValue = INT_MAX / 10;
      lineTree.Query(left, m_c - 1);
      return lineTree.m_iQueryValue+1;
    }
    int m_c;
  
  };

测试用例

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

}

扩展阅读

视频课程

有效学习：明确的目标及时的反馈拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。

https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程

https://edu.csdn.net/lecturer/6176

鄙人想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
墨家名称的来源：有所得以墨记之。
如果程序是一条龙，那算法就是他的是睛

测试环境

操作系统：win7 开发环境： VS2019 C++17

或者操作系统：win10 开发环境： VS2022 C++17

【线段树】【前缀和】：1687从仓库到码头运输箱子

本题简单解法

本文涉及的基础知识点

LeetCode1687从仓库到码头运输箱子

线段树

代码

核心代码

测试用例

扩展阅读

视频课程

相关下载

测试环境

热门文章

最新文章

相关电子书