LeetCode857-雇佣K名工人的最低成本

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/minimum-cost-to-hire-k-workers/

中文链接：https://leetcode-cn.com/problems/minimum-cost-to-hire-k-workers/

题目详述

有 N 名工人。 第 i 名工人的工作质量为 quality[i] ，其最低期望工资为 wage[i] 。

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

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

返回组成一个满足上述条件的工资组至少需要多少钱。

示例 1：

1
2
3
输入： quality = [10,20,5], wage = [70,50,30], K = 2
输出： 105.00000
解释： 我们向 0 号工人支付 70，向 2 号工人支付 35。

示例 2：

1
2
3
输入： quality = [3,1,10,10,1], wage = [4,8,2,2,7], K = 3
输出： 30.66667
解释： 我们向 0 号工人支付 4，向 2 号和 3 号分别支付 13.33333。

提示：

  1. 1 <= K <= N <= 10000，其中 N = quality.length = wage.length
  2. 1 <= quality[i] <= 10000
  3. 1 <= wage[i] <= 10000
  4. 与正确答案误差在 10^-5 之内的答案将被视为正确的。

题目详解

  • 由条件 1 可知，K 名工人的工资为 q[i] * x，x 为公因子。
  • 由条件 2 可知，对于任意的这 K 名工人，q[i] * x >= w[i]，则 x >= w[i] / q[i]。
  • 可以把工人按照 w / q 从小到大进行排序，这样以当前工人的 x 为基准，前面的工人必满足要求。
  • 问题就转化为了：每次以当前工人的 x 为基准，如何快速在前 i 个工人中选择 q 最小的 K 个工人。显然，构建一个大根堆可以解决此问题。
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
36
37
38
39
public class LeetCode_00857 {

    public double mincostToHireWorkers(int[] quality, int[] wage, int K) {
        Worker[] workers = new Worker[quality.length];
        for (int i = 0; i < quality.length; ++i) {
            workers[i] = new Worker((double) wage[i] / quality[i], quality[i]);
        }
        Arrays.sort(workers);
        double res = 1e9;
        Queue<Integer> queue = new PriorityQueue<>(Comparator.reverseOrder());
        int s = 0;
        for (Worker worker : workers) {
            s += worker.quality;
            queue.offer(worker.quality);
            if (queue.size() > K) {
                s -= queue.poll();
            }
            if (queue.size() == K) {
                res = Math.min(res, s * worker.x);
            }
        }
        return res;
    }

    class Worker implements Comparable<Worker> {
        double x;
        int quality;

        public Worker(double x, int quality) {
            this.x = x;
            this.quality = quality;
        }

        @Override
        public int compareTo(Worker o) {
            return Double.compare(x, o.x);
        }
    }
}