跳转至

857. 雇佣 K 名工人的最低成本

题目描述

有 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

解法

方法一：贪心 + 优先队列（大根堆）

我们假设选取了某一个工资组，总工作质量为 tot，总支付金额为 c。每个工人的工作质量为 $q_i$，工资为 $w_i$。那么，对于此工资组的每个工人，均满足 $c\times \frac{q_i}{tot} \ge w_i$。即 $c\ge tot\times \frac{w_i}{q_i}$。

在总工作质量 tot 固定的情况下，支付的金额取决于权重 $\frac{w_i}{q_i}$ 的最大值。

我们可以从小到大枚举权重 $\frac{w_i}{q_i}$ 作为工资组的最大值，此时工资组其他人员只需要在权重小于等于这个值的集合中，选取工作质量最小的 $k-1$ 名工人来组成工资组即可。因此，可以用优先队列（最大堆）维护工作质量最小的 $k-1$ 名工人。

时间复杂度 $O(n\log n)$，空间复杂度 $O(n)$。其中 $n$ 是工人数。

相似题目：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def mincostToHireWorkers(
        self, quality: List[int], wage: List[int], k: int
    ) -> float:
        t = sorted(zip(quality, wage), key=lambda x: x[1] / x[0])
        ans, tot = inf, 0
        h = []
        for q, w in t:
            tot += q
            heappush(h, -q)
            if len(h) == k:
                ans = min(ans, w / q * tot)
                tot += heappop(h)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public double mincostToHireWorkers(int[] quality, int[] wage, int k) {
        int n = quality.length;
        Pair[] t = new Pair[n];
        for (int i = 0; i < n; ++i) {
            t[i] = new Pair(quality[i], wage[i]);
        }
        Arrays.sort(t, (a, b) -> Double.compare(a.x, b.x));
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
        double ans = 1e9;
        int tot = 0;
        for (var e : t) {
            tot += e.q;
            pq.offer(e.q);
            if (pq.size() == k) {
                ans = Math.min(ans, tot * e.x);
                tot -= pq.poll();
            }
        }
        return ans;
    }
}

class Pair {
    double x;
    int q;

    Pair(int q, int w) {
        this.q = q;
        this.x = (double) w / q;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    double mincostToHireWorkers(vector<int>& quality, vector<int>& wage, int k) {
        int n = quality.size();
        vector<pair<double, int>> t(n);
        for (int i = 0; i < n; ++i) {
            t[i] = {(double) wage[i] / quality[i], quality[i]};
        }
        sort(t.begin(), t.end());
        priority_queue<int> pq;
        double ans = 1e9;
        int tot = 0;
        for (auto& [x, q] : t) {
            tot += q;
            pq.push(q);
            if (pq.size() == k) {
                ans = min(ans, tot * x);
                tot -= pq.top();
                pq.pop();
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
func mincostToHireWorkers(quality []int, wage []int, k int) float64 {
    t := []pair{}
    for i, q := range quality {
        t = append(t, pair{float64(wage[i]) / float64(q), q})
    }
    sort.Slice(t, func(i, j int) bool { return t[i].x < t[j].x })
    tot := 0
    var ans float64 = 1e9
    pq := hp{}
    for _, e := range t {
        tot += e.q
        heap.Push(&pq, e.q)
        if pq.Len() == k {
            ans = min(ans, float64(tot)*e.x)
            tot -= heap.Pop(&pq).(int)
        }
    }
    return ans
}

type pair struct {
    x float64
    q int
}

type hp struct{ sort.IntSlice }

func (h *hp) Push(v any) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() any {
    a := h.IntSlice
    v := a[len(a)-1]
    h.IntSlice = a[:len(a)-1]
    return v
}
func (h *hp) Less(i, j int) bool { return h.IntSlice[i] > h.IntSlice[j] }

评论