困难

问题描述

有 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

贪心 + 优先队列

将 $quality_i$ 视为每个工人的产出，而 $wage_i / quality_i$ 则为单位产出的价格。假设$[w_1, w_2, \dots, w_k]$ 为一个工资组，$w_i$ 为组内第 $i$ 个工人，$totalQ$ 为该工资组的产出总量，$totalW$ 为总支付工资，那么对于任意工人 $w_i$ 需要满足：

$$totalW \times \dfrac{quality_i}{totalQ} \geq wage_i$$

即：

$$totalW \geq totalQ \times \dfrac{wage_i}{quality_i}$$

当 $totalQ$ 固定时，$totalW$ 由最大的 $\dfrac{wage_i}{quality_i}$ 所决定，因此每个工人按照单位价格升序排列，再依次添加，这样就保证了最大的 $\dfrac{wage_i}{quality_i}$ 是最后添加的那个价格。同时，当 $\dfrac{wage_i}{quality_i}$ 固定时，$totalQ$ 越小越好，因此维护一个长度为 $k$ 的优先队列，存放前面的产量最少的 $k$ 个值，并维护它们的和。这样，遍历一次排序后的数组，查找出最小的结果即为答案。

/**
 * @param {number[]} quality
 * @param {number[]} wage
 * @param {number} k
 * @return {number}
 */
var mincostToHireWorkers = function (quality, wage, k) {
  const workers = quality.map((v, i) => [wage[i] / v, v]).sort((a, b) => a[0] - b[0])
  const queue = new MaxPriorityQueue()
  let ans = Number.MAX_VALUE
  let total = 0
  for (const worker of workers) {
    total += worker[1]
    queue.enqueue(worker[1])
    if (queue.size() > k) {
      total -= queue.dequeue().element
    }
    if (queue.size() === k) {
      ans = Math.min(ans, total * worker[0])
    }
  }
  return ans
}

• 时间复杂度：$O(n\log{n})$
• 空间复杂度：$O(n)$