Python程序：计算仓库中需要存放的箱子数量

假设我们有两个包含整数的数组。一个列表包含一些单位宽度箱子的高度，另一个数组包含仓库中房间的高度。房间编号为0...n，房间的高度在其在godown数组中的相应索引中提供。我们必须找出可以放入仓库的箱子数量。需要注意以下几点：

  • 箱子不能堆叠。

  • 箱子的顺序可以改变。

  • 箱子只能从左到右放入仓库。

如果箱子比房间的高度高，则该箱子及其右侧的所有箱子都不能放入仓库。

因此，如果输入类似于boxes = [4,5,6], godown = [4, 5, 6, 7]，则输出将为1。只能插入一个箱子。第一个房间的大小为4，其余箱子不能放入仓库，因为箱子必须穿过第一个房间，而第一个房间的长度小于其他箱子。

为了解决这个问题，我们将遵循以下步骤：

  • 对列表boxes进行排序

  • curmin := 一个新列表，包含godown的第一个元素

  • cm := curmin[0]

  • 对于范围1到godown大小的i，执行：

    • cur := godown[i]

    • 如果 cur < cm，则

      • cm := cur

    • 将cm插入curmin的末尾

  • i := 0

  • j := godown的大小 - 1

  • r := 0

  • 当 j >= 0 且 i < boxes的大小时，执行：

    • 如果 curmin[j] >= boxes[i]，则

      • i := i + 1

      • r := r + 1

    • j := j - 1

  • 返回 r

示例 (Python)

让我们看看下面的实现，以便更好地理解：

 在线演示

def solve(boxes, godown):
   boxes.sort()
   curmin = [godown[0]]
   cm = curmin[0]
   for i in range(1, len(godown)):
      cur = godown[i]
      if cur < cm:
         cm = cur
      curmin.append(cm)
   i,j = 0, len(godown)-1
   r = 0
   while j >= 0 and i < len(boxes):
      if curmin[j] >= boxes[i]:
         i += 1
         r += 1
      j -= 1
   return r

print(solve([4,5,6], [4, 5, 6, 7]))

输入

[4,5,6], [4, 5, 6, 7]

输出

1

更新于：2021年5月18日

292 次浏览

开启你的职业生涯

通过完成课程获得认证

开始学习
广告
© . All rights reserved.