857. 雇佣 K 名工人的最低成本 : 枚举 + 优先队列（堆）运用题

站长

2023年08月11日 09:14 · 阅读数 14

我报名参加金石计划一期挑战——瓜分10万奖池，这是我的第9篇文章，点击查看活动详情

题目描述

这是 LeetCode 上的 857. 雇佣 K 名工人的最低成本 ，难度为困难。

Tag : 「枚举」、「优先队列（堆）」

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

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

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

给定整数 k，返回组成满足上述条件的付费群体所需的最小金额。在实际答案的 10−510^{-5}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.lengthn = quality.length = wage.lengthn=quality.length=wage.length
1<=k<=n<=1041 <= k <= n <= 10^41<=k<=n<=104
1<=quality[i],wage[i]<=1041 <= quality[i], wage[i] <= 10^41<=quality[i],wage[i]<=104

枚举 + 优先队列（堆）

为了方便，我们令 quality 为 qs，wage 为 ws。

从 nnn 个工人中选 kkk 个，使这 kkk 个工人实际工资与其 qs[i]qs[i]qs[i] 成比例，且实际工资不低于 ws[i]ws[i]ws[i]。

根据条件一，假设实际工资与能力值比值为 ttt，则所选工人的实际工资为 qs[i]×tqs[i] \times tqs[i]×t，再结合条件二可知 qs[i]×t>=ws[i]qs[i] \times t >= ws[i]qs[i]×t>=ws[i]，变形可得 t>=ws[i]qs[i]t >= \frac{ws[i]}{qs[i]}t>=qs[i]ws[i]。

那么在选定若干工人的情况下，为使得总支出最小，我们可以取 ttt 为所有被选工人中的最大 ws[i]qs[i]\frac{ws[i]}{qs[i]}qs[i]ws[i] 即可。

因此最终的 ttt 值必然是取自某个工人的实际比值 ws[i]qs[i]\frac{ws[i]}{qs[i]}qs[i]ws[i]，这引导我们可以通过「枚举」哪个工人的实际比值为实际 ttt 值来做。

假设我们已经预处理出所有工人的 ws[i]qs[i]\frac{ws[i]}{qs[i]}qs[i]ws[i] 比值信息，并「从小到大」进行枚举（该过程可看做是以比值信息作为维度来枚举每个工人）：假设当前处理到的比值为最终使用到的 ttt，我们能够选的工人必然是在该工人的左边（根据上述分析可知，被选的工人满足 ws[i]qs[i]<=t\frac{ws[i]}{qs[i]} <= tqs[i]ws[i]<=t 条件）。

因此，我们可以使用二维数组 ds 记录下每个工人的 ws[i]qs[i]\frac{ws[i]}{qs[i]}qs[i]ws[i] 比值信息：ds[i][0]=ws[i]qs[i]ds[i][0] = \frac{ws[i]}{qs[i]}ds[i][0]=qs[i]ws[i]，ds[i][1]=ids[i][1] = ids[i][1]=i。并对其进行排升序，枚举每个工人的实际比值，同时动态维护枚举过程中的最小 kkk 个 qs[i]qs[i]qs[i]（使用「大根堆」处理），并使用单变量 tot 记录当前堆中的 qs[i]qs[i]qs[i] 总和，tot×ws[i]qs[i]tot \times \frac{ws[i]}{qs[i]}tot×qs[i]ws[i] 即是以当前比值作为实际 ttt 值时的总成本，在所有总成本中取最小值即是答案。

Java 代码：

class Solution {
    public double mincostToHireWorkers(int[] qs, int[] ws, int k) {
        int n = qs.length;
        double[][] ds = new double[n][2];
        for (int i = 0; i < n; i++) {
            ds[i][0] = ws[i] * 1.0 / qs[i]; ds[i][1] = i * 1.0;
        }
        Arrays.sort(ds, (a,b)->Double.compare(a[0], b[0]));
        PriorityQueue<Integer> q = new PriorityQueue<>((a,b)->b-a);
        double ans = 1e18;
        for (int i = 0, tot = 0; i < n; i++) {
            int cur = qs[(int)ds[i][1]];
            tot += cur; q.add(cur);
            if (q.size() > k) tot -= q.poll();
            if (q.size() == k) ans = Math.min(ans, tot * ds[i][0]);
        }
        return ans;
    }
}

TypeScript 代码：

function mincostToHireWorkers(qs: number[], ws: number[], k: number): number {
    const n = qs.length
    const ds: number[][] = new Array<Array<number>>()
    for (let i = 0; i < n; i++) ds.push([ws[i] / qs[i], i])
    ds.sort((a,b)=>a[0]-b[0])
    const q = new MaxPriorityQueue()
    let ans = 1e18
    for (let i = 0, tot = 0; i < n; i++) {
        const cur = qs[ds[i][1]]
        tot += cur
        q.enqueue(cur)
        if (q.size() > k) tot -= q.dequeue().element
        if (q.size() == k) ans = Math.min(ans, tot * ds[i][0])
    }
    return ans
};

时间复杂度：构造系数并排序复杂度为 O(nlog⁡n)O(n\log{n})O(nlogn)；枚举并计算答案复杂度为 O(nlog⁡k)O(n\log{k})O(nlogk)。整体复杂度为 O(nlog⁡n)O(n\log{n})O(nlogn)
空间复杂度：O(n)O(n)O(n)

最后

这是我们「刷穿 LeetCode」系列文章的第 No.857 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

更多更全更热门的「笔试/面试」相关资料可访问排版精美的合集新基地 🎉🎉