LeetCode.857 Minimum Cost to Hire K Workers

题目地址

题意:

n个人,每个人有wage和quality,选择K个人按照quality比发放工资,要求到手的工资不少于各自的wage,求最小花费。

思路:

考虑选中的K个人中,如果以满足第$i$个人的wage为标准发放工资,则最后的花费$Q$为:

为了满足其他人的工资不低于各自的wage:

所以$i$号人的$\frac { w }{ q } $应该是最大的。 所以只需要对$\frac { w }{ q } $进行排序,然后计算前$i$个人中,最小的K个quality的和就行了,优先队列或者大根堆维护即可。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
def mincostToHireWorkers(self, quality, wage, K):
"""
:type quality: List[int]
:type wage: List[int]
:type K: int
:rtype: float
"""
a = [(w/q, w, q) for (w, q) in zip(wage, quality)]
a.sort()
import queue as Q
q = Q.PriorityQueue()
ans = -1
tot = 0
for i in range(len(a)):
if(q.qsize() >= K):
tot -= -q.get_nowait()
tot += a[i][2]
q.put(-a[i][2])
if(q.qsize() >= K and (tot*a[i][0]<ans or ans==-1)):
ans = tot*a[i][0]
return ans