用 Python 编写程序，找出雇用 k 名工人的最低成本

pythonserver side programmingprogramming更新于 2025/12/9 16:12:17

假设我们为每位不同的工人设置了一个名为 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 := a new列表
对于 quality 和 wage 中的每个对 (q, w)，执行
- 在 qr 末尾插入 (w/q, q)
对列表 qr 进行排序
cand := 一个新列表，csum := 0
对于范围从 0 到 K - 1 的 i，执行
- 将 -qr[i, 1] 插入堆 cand
- csum := csum + qr[i, 1]
ans := csum * qr[K - 1, 0]
对于idx 在范围 K 到质量大小之间，执行
- 将 -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))