857_雇佣_K_名工人的最低成本

类型：堆

1. 雇佣 K 名工人的最低成本 ❤️ ⭐
https://leetcode-cn.com/problems/minimum-cost-to-hire-k-workers/

参见：力扣加加

❓ 有 N 名工人。数组 quality 表明了每个人的工作质量，数组 wage 表明了每个人的期望薪资。我们现在要从中雇佣 K 个人，在工资支付上我们需要遵从如下要求：
- 每个人的薪资都不能低于其期望值
- 工人们的薪资比要符合他们的工作质量之比
求我们雇佣 K 个人的最低成本。

💡 堆

花最少的钱，则必然至少有一位员工拿的是其最低期望工资。以此为基准根据工作质量比计算其他人的工资。

员工价值 R = w / q 如果一个员工的价值为 R，当他恰好拿到最低工资时，所有价值高于 R 的员工都无法拿到预期工资，而所有价值低于 R 的员工都能拿得比预期工资多。我们可以将员工按照价值从小到大排列，当我们以第 i 位员工的预期工资作为薪资标准时，则包括 i 在内的前 i 位员工是可以被招聘的，i 之后的员工则无法被招聘。

通过员工价值，我们判断出了在具体工资标准下，哪些员工可被招聘。即员工价值决定了该员工能不能被招来。

当我们设定以第 i 为员工作为薪资标准后。我们可以从 1 ～ i 号员工中选出 k 位，达到最低工资开销。

这 k 为该怎么选呢，也是根据员工价值吗？不是的。当我们选定了 i 号员工作为基准后，就相当于选定了以 i 号员工的价值作为所有原有员工的价值。此时其他员工的实际价值就已经没有意义了。由于此题只关注员工数量，不关注实际工作产出量，在价值确定的情况下，我们倾向于工作质量（效率）低员工，因为你工作质量越高，干得活越多，我们就要给你越多的钱。
```
class Solution:
    def mincostToHireWorkers(self, quality: List[int], wage: List[int], K: int) -> float:
        from fractions import Fraction
        workers = sorted([(Fraction(w, q), q, w) for q, w in zip(quality, wage)])

        ans = float('inf')
        pool = []
        for ratio, q, w in workers:
            if not pool or len(pool) < K or q <= -1 * min(pool):
                heapq.heappush(pool, -q)

            if len(pool) > K:
                heapq.heappop(pool)

            if len(pool) == K:
                ans = min(ans, -1 * sum(pool) * ratio)
        return ans
```
时间复杂度：O(NlogN)，空间复杂度：O(N)