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$

列舉 + 優先佇列（堆）

為了方便，我們令 quality 為 qs ， wage 為 ws 。

從 $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 道題目，部分是有鎖題，我們將先把所有不帶鎖的題目刷完。

在這個系列文章裡面，除了講解解題思路以外，還會盡可能給出最為簡潔的程式碼。如果涉及通解還會相應的程式碼模板。

為了方便各位同學能夠電腦上進行除錯和提交程式碼，我建立了相關的倉庫： http://github.com/SharingSou... 。

在倉庫地址裡，你可以看到系列文章的題解連結、系列文章的相應程式碼、LeetCode 原題連結和其他優選題解。

更多更全更熱門的「筆試/面試」相關資料可訪問排版精美的合集新基地 :tada::tada:

本文由mdnice多平臺釋出