Python程式：查詢僱傭k個員工的最低成本

假設我們有一個名為quality的陣列，用於表示每個不同工人的質量，還有一個名為wages的陣列表示工資，以及一個值K。第i個工人具有quality[i]的質量和最低工資期望wage[i]。我們想僱傭K個工人來組成一個付費小組。當我們僱傭一個由K個工人組成的團隊時，我們必須根據以下規則支付他們

  • 付費小組中的每個工人的工資應與其在付費小組中其他工人的質量相比成比例。

  • 付費小組中的每個工人都必須獲得至少其最低工資期望。

我們必須找到滿足上述條件的付費小組所需的最低金額。

因此，如果輸入類似於quality = [10,22,5]，wage = [70,52,30]和K = 2，則輸出將為105.000，因為我們將向第一位工人支付70，向第三位工人支付35。

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

  • qr := 一個新的列表

  • 對於quality和wage中的每個(q, w)對，執行以下操作：

    • 將(w/q, q)插入qr的末尾

  • 對列表qr進行排序

  • cand := 一個新的列表，csum := 0

  • 對於i從0到K - 1，執行以下操作：

    • 將-qr[i, 1]插入堆cand中

    • csum := csum + qr[i, 1]

  • ans := csum * qr[K - 1, 0]

  • 對於idx從K到quality的大小，執行以下操作：

    • 將-qr[i, 1]插入堆cand中

    • csum := csum + qr[idx, 1] + 堆cand中的頂部元素，並將其從堆中刪除

    • ans = ans和(csum * qr[idx][0])的最小值

  • 返回ans

示例

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

import heapq
def solve(quality, wage, K):
   qr = []
   for q, w in zip(quality, wage):
      qr.append([w/q, q])
   qr.sort()

   cand, csum = [], 0
   for i in range(K):
      heapq.heappush(cand, -qr[i][1])
      csum += qr[i][1]
   ans = csum * qr[K - 1][0]

   for idx in range(K, len(quality)):
      heapq.heappush(cand, -qr[idx][1])
      csum += qr[idx][1] + heapq.heappop(cand)
      ans = min(ans, csum * qr[idx][0])
   return ans

quality = [10,22,5]
wage = [70,52,30]
K = 2
print(solve(quality, wage, K))

輸入

[10,22,5], [70,52,30], 2

輸出

105

更新於: 2021年10月7日

276次瀏覽

啟動你的職業生涯

透過完成課程獲得認證

開始
廣告