在 Python 中找到雇用 k 个工人的最低成本的程序

• Z时代
• 2024-01-10
• 分类：综合

假设我们为每个不同的工人有一个名为 quality 的数组，还有另一个名为工资的数组和一个值 K。第 i 个工人有一个 quality[i] 和一个最低工资期望工资 [i]。我们想雇佣 K 个工人组成一个有偿小组。当我们雇佣一组K个工人时，我们必须按照以下规则支付工资：

• 有偿组中的每个工人应通过与有偿组中的其他人进行比较，按其质量的比例获得报酬。

• 受薪组中的每个工人都必须至少获得他们的最低工资预期。

我们必须找到满足上述条件的付费组所需的最少金额。

因此，如果输入类似于质量 = [10,22,5]，工资 = [70,52,30] 和 K = 2，那么输出将为 105.000，因为我们将向第一个工人支付 70，向第一个工人支付 35 3号工人。

示例

让我们看下面的实现来更好地理解

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

以上是 在 Python 中找到雇用 k 个工人的最低成本的程序 的全部内容， 来源链接： utcz.com/z/317271.html