雇佣 K 名工人的最低成本

标签: 贪心 数组 排序 堆（优先队列）

难度: Hard

有 n 名工人。 给定两个数组 quality 和 wage ，其中，quality[i] 表示第 i 名工人的工作质量，其最低期望工资为 wage[i] 。

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

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

给定整数 k ，返回 组成满足上述条件的付费群体所需的最小金额 。在实际答案的 10-5 以内的答案将被接受。。

示例 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。

提示：

  • n == quality.length == wage.length
  • 1 <= k <= n <= 104
  • 1 <= quality[i], wage[i] <= 104

Submission

运行时间: 55 ms

内存: 18.1 MB

class Solution:
    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:
        idx=[x for x in range(len(quality))]
        idx.sort(key=lambda x:wage[x]/quality[x], reverse=True)
        
        h=[]
        for y in range(1,k):
            heappush(h,-quality[idx[-y]])
        s=-sum(h)
        res=float("inf")
        
        for z in reversed(range(len(idx)-k+1)):
            unitwage=wage[idx[z]]/quality[idx[z]]
            res=min(res,wage[idx[z]]+unitwage*s)
            s+=quality[idx[z]]
            s+=heappushpop(h,-quality[idx[z]])
        return res

Explain

此题的关键是如何以最低成本雇佣k名工人。要求每名工人的工资与他们的工作质量成比例，且不低于他们的最低期望工资。首先，我们需要确定支付给每位工人的单位工资（即工资与质量的比率）。题解中采用了一个贪心策略，按照每位工人的单位工资从高到低排序。然后使用一个最大堆来维护当前选择的工人的质量总和，堆的大小维持为k-1，这样可以在添加新的工人时，快速计算出增加的总成本。对于每个工人，计算包括他在内的k个工人的总成本，并更新最小成本。最小成本是通过当前工人的期望工资加上其他k-1个工人的工资总和（由单位工资乘以他们的质量总和得到）来计算。

时间复杂度: O(n log n)

空间复杂度: O(n)

class Solution:
    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:
        idx = [x for x in range(len(quality))]
        # 根据工资/质量比率从高到低排序工人
        idx.sort(key=lambda x: wage[x] / quality[x], reverse=True)
        
        h = []  # 使用最大堆来维护当前选择的工人的质量总和
        for y in range(1, k):
            heappush(h, -quality[idx[-y]])  # 添加k-1个工人到堆中
        s = -sum(h)  # 计算堆中质量的总和
        res = float("inf")  # 初始化最小成本为无穷大
        
        for z in reversed(range(len(idx) - k + 1)):
            unitwage = wage[idx[z]] / quality[idx[z]]  # 当前工人的单位工资
            res = min(res, wage[idx[z]] + unitwage * s)  # 更新最小成本
            s += quality[idx[z]]  # 更新包含新工人的质量总和
            s += heappushpop(h, -quality[idx[z]])  # 调整堆，并更新质量总和
        
        return res  # 返回最小成本

Explore

按照单位工资从高到低进行排序可以帮助我们在遍历工人时，始终保持当下正在考虑的工人有最低的单位工资。这种方式有效地将问题转化为：一旦选定了某个工人作为单位工资的基准（即当前遍历到的工人），只需要考虑如何以此单位工资最小化其他工人的成本。这样可以确保在满足k个工人的条件下，总成本尽可能低，因为随着遍历的进行，单位工资会逐渐减小，我们只需要关注在这个单位工资下，如何选择其他k-1个工人使得成本最低。

最大堆在此代码中用来维护当前选择的k-1个工人的质量。使用最大堆的原因是，当我们需要添加一个新工人到已经选定的k-1个工人中时，我们可能需要替换掉其中某个工人以保证总成本最低。最大堆允许我们快速识别出当前质量最大的工人（即堆顶元素），并在必要时将其替换出去，这样可以确保我们总是尽可能地减少质量总和，从而在给定的单位工资下最小化总成本。

在初始化堆时只添加k-1个工人的质量，是为了在后续的迭代中方便地计算包括当前考虑的工人在内的总成本。如果堆中已经包含了k-1个工人的质量，当考虑一个新的工人时，只需将这个新工人的质量加到堆的质量总和中，就可以直接计算出包括这个新工人在内的k个工人的总成本。如果堆中已经有k个工人的质量，那么每次考虑新工人时，我们不仅需要添加这个新工人的质量，还必须从堆中移除一个工人的质量，这将增加额外的复杂度和运算量。