Leetcode 857:雇佣 K 名工人的最低成本(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 857:雇佣 K 名工人的最低成本(超详细的解法!!!)

in leetcode with 0 comment

N名工人。 第i名工人的工作质量为quality[i],其最低期望工资为wage[i]

现在我们想雇佣K名工人组成一个工资组。在雇佣 一组K名工人时,我们必须按照下述规则向他们支付工资:

  1. 对工资组中的每名工人,应当按其工作质量与同组其他工人的工作质量的比例来支付工资。
  2. 工资组中的每名工人至少应当得到他们的最低期望工资。

返回组成一个满足上述条件的工资组至少需要多少钱。

示例 1:

输入: quality = [10,20,5], wage = [70,50,30], K = 2
输出: 105.00000
解释: 我们向 0 号工人支付 70,向 2 号工人支付 35。

示例 2:

输入: quality = [3,1,10,10,1], wage = [4,8,2,2,7], K = 3
输出: 30.66667
解释: 我们向 0 号工人支付 4,向 2 号和 3 号分别支付 13.33333。

提示:

  1. 1 <= K <= N <= 10000,其中N = quality.length = wage.length
  2. 1 <= quality[i] <= 10000
  3. 1 <= wage[i] <= 10000
  4. 与正确答案误差在10^-5之内的答案将被视为正确的。

解题思路

读完题目的第一观感就是要挑选wage小的工人,但这样就不合理,因为如果quality很小的话。例如,第一个例子,选择02工人比选12工人更好。不难看出wage大的工人其quality要尽可能的大(也就是wage/quality要小)。

我们定义P=wage/quality,最后统计工资的时候,就是所有工人的quality累加乘上P就是最少花多少钱。例如,第一个列子:

70/10 = 7
30/5 = 6
-------------
15 * 7 = 105

如果有一个工人比值为P,那么那些比值高于P的工人显然无法拿到最低期望工资,而比值小于P的工人可以拿到比最低期望工资高的工资,也就是说P是最后K个工人中的最大比值。

首先我们可以对所有工人按照P值从小到大排序,然后从前向后遍历排好序的工人。假设此时遍历到第i个工人(如果以这个工人作为P),那么index小于i的工人都可以拿到最低期望工资,所以我们需要从这里面选择K-1quality最小的工人。

class Solution:
    def mincostToHireWorkers(self, quality: List[int], wage: List[int], K: int) -> float:
        workers = sorted([[w / q, q] for w, q in zip(wage, quality)])
        res, qsum = float('inf'), 0
        heap = []

        for r, q in workers:
            qsum += q
            if len(heap) == K - 1: res = min(res, qsum * r)
            heapq.heappush(heap, -q)
            if len(heap) >= K: qsum += heapq.heappop(heap)
        return res

reference:

https://leetcode.com/problems/minimum-cost-to-hire-k-workers/discuss/141768/Detailed-explanation-O(NlogN)

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses