Python程式：求解銷售價值遞減彩色球的最大利潤

假設我們有一個名為 inventory 的陣列，其中 inventory[i] 表示我們最初擁有的第 i 種顏色球的數量。我們還有一個名為 orders 的值，它表示客戶想要購買的球的總數。我們可以按任意順序出售這些球。在我們的 inventory 中有不同顏色的球，客戶想要任何顏色的球。現在，這些球的價值具有特殊的性質。每種顏色球的價值是我們在庫存中擁有的該顏色球的數量。因此，如果我們目前有 6 個藍色球，客戶將為第一個藍色球支付 6。然後只剩下 5 個藍色球，所以下一個藍色球的價值為 5。我們必須找到在出售 orders 個彩色球后可以獲得的最大總價值。如果答案過大，則返回它對 10^9 + 7 取模的結果。

因此，如果輸入類似於 inventory = [5,7]，orders = 6，則輸出將為 31，因為我們可以以價格 (5,4) 出售第一種顏色球兩次，以價格 (7,6,5,4) 出售第二種顏色球 4 次，因此總利潤為 5+4+7+6+5+4 = 31

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

  • low := 0, high := 10000000

  • 當 low < high 時，執行以下操作：

    • mid := (low + high) / 2 的商

    • s := 0

    • 對於 inventory 中的每個 i，執行以下操作：

      • 如果 i > mid，則

        • s := s + i - mid

    • 如果 s > orders，則

      • low := mid + 1

    • 否則，

      • high := mid

  • mid := (low + high) / 2 的商

  • ans := 0

  • 對於 inventory 中的每個 i，執行以下操作：

    • 如果 i > mid，則

      • ans := ans + (i*(i+1)/2) 的商 - (mid*(mid+1)/2) 的商

      • orders := orders - i - mid

  • ans := ans + orders * mid

  • 返回 ans mod (10^9 + 7)

示例

讓我們檢視以下實現以更好地理解：

def solve(inventory, orders):
   low = 0
   high = 10000000

   while low < high:
      mid = (low+high)//2

      s = 0
      for i in inventory:
         if i > mid:
            s += i-mid

      if s > orders:
         low = mid+1
      else:
         high = mid


   mid = (low+high)//2

   ans = 0
   for i in inventory:
      if i > mid:
         ans += i*(i+1)//2 - mid*(mid+1)//2
         orders -= i-mid

   ans += orders*mid
   return ans % (10**9 + 7)

inventory = [5,7]
orders = 6
print(solve(inventory, orders))

輸入

[6,8,7,11,5,9], [0,0,2], [2,3,5]

輸出

31

更新於: 2021年10月6日

232 次瀏覽

開啟你的職業生涯

透過完成課程獲得認證

立即開始
廣告