在 Python 中找到雇用 k 个工人的最低成本的程序
假设我们为每个不同的工人有一个名为quality的数组，还有另一个名为工资的数组和一个值K。第i个工人有一个quality[i]和一个最低工资期望工资[i]。我们想雇佣K个工人组成一个有偿小组。当我们雇佣一组K个工人时，我们必须按照以下规则支付工资：
有偿组中的每个工人应通过与有偿组中的其他人进行比较，按其质量的比例获得报酬。
受薪组中的每个工人都必须至少获得他们的最低工资预期。
我们必须找到满足上述条件的付费组所需的最少金额。
因此，如果输入类似于质量=[10,22,5]，工资=[70,52,30]和K=2，那么输出将为105.000，因为我们将向第一个工人支付70，向第一个工人支付353号工人。
示例
让我们看下面的实现来更好地理解
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