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.