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

示例

让我们看看以下实现以更好地理解

Open Compiler
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

Learn Python in-depth with real-world projects through our Python certification course. Enroll and become a certified expert to boost your career.

输出

105

更新于: 2021年10月7日

276次浏览

启动你的职业生涯

通过完成课程获得认证

开始
广告