在 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