在 Python 中查詢購買所有 N 個糖果的最小和最大金額

假設有一家糖果店，出售 N 種不同型別的糖果，並且所有 N 種不同型別糖果的價格都已給出。該商店還提供一項有吸引力的優惠。根據此優惠，我們可以從商店購買一件糖果，並最多免費獲得 K 種其他不同型別的糖果。我們必須找到購買所有 N 種不同型別糖果所需的最低金額。我們還必須找到購買所有 N 種不同型別糖果所需的最大金額。在這兩種情況下，我們都必須利用優惠並獲得儘可能多的糖果。如果有 k 個或更多糖果可用，我們必須為每次購買糖果選擇 k 個糖果。但是，如果可用糖果少於 k 個，則我們必須為每次購買糖果選擇所有糖果。

因此，如果輸入類似於 price = [4, 3, 2, 5] 且 k = 2，則輸出將為 Minimum = 5 且 Maximum = 9。這是因為當 k 為 2 時，如果我們購買一個糖果，我們可以免費獲得最多兩個糖果。在第一種情況下，我們可以購買價格為 2 的糖果，並免費獲得價格為 4 和 5 的糖果，我們也可以購買價格為 3 的糖果，因此最低成本 = 2 + 3 = 5。另一方面，在第二種情況下，我們購買價格為 5 的糖果，並免費獲得價格為 2 和 3 的糖果，或者我們也可以購買價格為 4 的糖果。因此，最大成本 = 4 + 5 = 9。

要解決此問題，我們將遵循以下步驟：

  • 定義一個函式 get_min()。這將接收 A、k。

  • n := A 的大小

  • 對列表 A 進行排序

  • res := 0，i:= 0

  • 當 n 不為零時，執行以下操作：

    • res := res + A[i]

    • n := n-k

    • i := i + 1

  • 返回 res

  • 定義一個函式 get_max()。這將接收 A、k。

  • n := A 的大小

  • 對列表 A 進行排序

  • res := 0，idx := 0

  • i:= n-1

  • 當 i>=idx 時，執行以下操作：

    • res := res + A[i]

    • idx := idx + k

    • i := i - 1

  • 返回 res

  • 從主方法呼叫這兩個函式以獲取結果

  • get_min(A, k)

  • get_max(A, k)

示例

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

即時演示

def get_min(A,k):
   n = len(A)
   A.sort()
   res = 0
   i=0
   while(n):
      res += A[i]
      n = n-k
      i += 1
   return res
def get_max(A, k):
   n = len(A)
   A.sort()
   res = 0
   idx = 0
   i=n-1
   while(i>=idx):
      res += A[i]
      idx += k
      i -= 1
   return res

A = [4, 3, 2, 5]
k = 2
print(get_min(A, k),get_max(A, k))

輸入

[4, 3, 2, 5], 2

輸出

5 9

更新於: 2020-08-20

834 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始
廣告