数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究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
示例
让我们看看以下实现以更好地理解
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
更新于: 2021年10月7日
276次浏览
广告