在Python中寻找雇用K名工人的最小费用

假设我们有一个名为quality的数组，每个工人都有一个希望达到的最低工资期望wage[i]和一个质量quality[i]。我们想雇用K名工人组成有偿团队，我们必须根据以下规则支付他们薪水：

有偿团队中的每个工人都应根据他们的质量与有偿团队中的其他工人进行比较，按比例支付。
有偿团队中的每个工人都必须至少按其最低工资期望获得报酬。

我们必须找到形成满足上述条件的有偿团队所需的最少金额。

因此，如果输入是quality = [10、22、5]，wage = [70、52、30]和K = 2，则输出将为105.000，因为我们将向第一个工人支付70元，并向第3个工人支付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]
对于从K到quality大小的范围中的每个idx，执行以下操作
- 将-qr[i,1]插入堆cand
- csum := csum + qr[idx,1] +来自堆的顶部元素并从堆中将其删除
- 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))