Python程式：計算摩天輪最大利潤所需的最少旋轉次數

假設有一個摩天輪，有四個座艙，每個座艙可容納四名乘客。摩天輪逆時針旋轉，每次旋轉需要花費“run”金額。現在我們有一個數組“cust”，包含n個專案，每個專案i表示在第i次旋轉前等待進入摩天輪的人數。為了登上摩天輪，每位顧客必須支付“board”金額，該金額用於摩天輪一次逆時針旋轉。排隊等待的人如果摩天輪有任何空位，則不應該等待。因此，給定資料，我們必須找出所需的最少旋轉次數，以便利潤最大化。

因此，如果輸入類似於 cust = [6,4]，board = 6，run = 4，則輸出為 3

首先，有6人在排隊。所以首先4人進入第一個座艙，其餘的人等待下一個座艙。

摩天輪旋轉，第二個座艙到達。同時，又有4人排隊。所以接下來等待的4人進入下一個座艙。

摩天輪再次旋轉，剩餘的三名顧客進入下一個座艙。

因此，最少需要三次旋轉才能服務所有顧客。

從這些旋轉中獲得的最大利潤是 (10 * 6) - (3 * 4) = 48。

為了解決這個問題，我們將遵循以下步驟：

  • res := -1

  • mst := 0

  • tmp := 0

  • wt := 0

  • 對於cust中的每個索引idx和值val，執行：

    • wt := wt + val

    • chg := min(4, wt)

    • wt := wt - chg

    • tmp := tmp + chg * board - run

    • 如果 mst < tmp，則：

      • res := idx + 1

      • mst := tmp

  • x := wt / 4

  • y := wt % 4

  • 如果 4 * board > run，則：

    • res := res + x

  • 如果 y * board > run，則：

    • res := res + 1

  • 返回 res

示例

讓我們看看下面的實現來更好地理解

def solve(cust, board, run):
   res = -1
   mst = 0
   tmp = 0
   wt = 0
   for idx, val in enumerate(cust):
      wt += val
      chg = min(4, wt)
      wt -= chg
      tmp += chg * board - run
      if mst < tmp:
         res, mst = idx+1, tmp
   x, y = divmod(wt, 4)
   if 4 * board > run:
      res += x
   if y * board > run:
      res += 1
   return res

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

輸入

[6,4], 6, 4

輸出

3

更新於：2021年10月6日

127 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告