LeetCode.857 Minimum Cost to Hire K Workers

题目地址

题意：

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

思路：

考虑选中的K个人中，如果以满足第\(i\)个人的wage为标准发放工资，则最后的花费\(Q\)为：

\[Q=\sum _{ k }^{ K }{ { q }_{ k } } \cdot \frac { { w }_{ i } }{ { q }_{ i } } \]

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

\[\frac { { w }_{ i } }{ { q }_{ i } } \cdot {q}_{j} \ge {w}_{j} (j\neq i)\]

即

\[\frac { { w }_{ i } }{ { q }_{ i } } \ge \frac { { w }_{ j } }{ { q }_{ j } } (j\neq i)\]

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

代码：

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