乐趣区

关于后端:857-雇佣-K-名工人的最低成本-枚举-优先队列堆运用题

题目形容

这是 LeetCode 上的 857. 雇佣 K 名工人的最低老本 ,难度为 艰难

Tag :「枚举」、「优先队列(堆)」

n 名工人。给定两个数组 quality 和 wage,其中,quality[i] 示意第 i 名工人的工作品质,其最低冀望工资为 wage[i]

当初咱们想雇佣 k 名工人组成一个工资组。在雇佣 一组 k 名工人时,咱们必须依照下述规定向他们领取工资:

  • 对工资组中的每名工人,该当按其工作品质与同组其余工人的工作品质的比例来领取工资。
  • 工资组中的每名工人至多该当失去他们的最低冀望工资。

给定整数 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 <= 10^4$
  • $1 <= quality[i], wage[i] <= 10^4$

枚举 + 优先队列(堆)

为了不便,咱们令 qualityqswagews

从 $n$ 个工人当选 $k$ 个,使这 $k$ 个工人实际工资与其 $qs[i]$ 成比例,且实际工资不低于 $ws[i]$。

依据条件一,假如实际工资与能力值比值为 $t$,则所选工人的实际工资为 $qs[i] \times t$,再联合条件二可知 $qs[i] \times t >= ws[i]$,变形可得 $t >= \frac{ws[i]}{qs[i]}$。

那么在选定若干工人的状况下,为使得总支出最小,咱们能够取 $t$ 为所有被选工人中的最大 $\frac{ws[i]}{qs[i]}$ 即可。

因而最终的 $t$ 值必然是取自某个工人的理论比值 $\frac{ws[i]}{qs[i]}$,这疏导咱们能够通过「枚举」哪个工人的理论比值为理论 $t$ 值来做。

假如咱们曾经预处理出所有工人的 $\frac{ws[i]}{qs[i]}$ 比值信息,并「从小到大」进行枚举(该过程可看做是以比值信息作为维度来枚举每个工人):假如以后解决到的比值为最终应用到的 $t$,咱们可能选的工人必然是在该工人的右边(根据上述剖析可知,被选的工人满足 $\frac{ws[i]}{qs[i]} <= t$ 条件)。

因而,咱们能够应用二维数组 ds 记录下每个工人的 $\frac{ws[i]}{qs[i]}$ 比值信息:$ds[i][0] = \frac{ws[i]}{qs[i]}$,$ds[i][1] = i$。并对其进行排升序,枚举每个工人的理论比值,同时动静保护枚举过程中的最小 $k$ 个 $qs[i]$(应用「大根堆」解决),并应用单变量 tot 记录以后堆中的 $qs[i]$ 总和,$tot \times \frac{ws[i]}{qs[i]}$ 即是以以后比值作为理论 $t$ 值时的总成本,在所有总成本中取最小值即是答案。

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(n\log{n})$;枚举并计算答案复杂度为 $O(n\log{k})$。整体复杂度为 $O(n\log{n})$
  • 空间复杂度:$O(n)$

最初

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

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

为了不便各位同学可能电脑上进行调试和提交代码,我建设了相干的仓库:https://github.com/SharingSou…。

在仓库地址里,你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。

更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉

本文由 mdnice 多平台公布

退出移动版