图解LeetCode——857. 雇佣 K 名工人的最低成本（难度：困难）

一、题目

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

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

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

给定整数 k ，返回 组成满足上述条件的付费群体所需的最小金额 。在实际答案的 10^-5 以内的答案将被接受。。

二、示例

2.1> 示例 1：

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

2.2> 示例 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我们可以将其比喻成行驶距离，quality=[2, 5, 10]；wage表示最低消耗的油量，wage=[40, 75, 80]。那么：

• 第一辆车是法拉利，但是要求单次最短出租公里数是2公里，最低加油量是40L，百公里最低油耗是40/2=20L/公里；
• 第二辆车是奔驰G，但是要求单次最短出租公里数是5公里，最低加油量是75L，百公里最低油耗75/5=15L/公里；
• 第三辆车是奥迪A4L，但是要求单次最短出租公里数是10公里，最低加油量是80L，百公里最低油耗80/10=8L/公里。

如果小明如果想同时租两款车，选择如下哪个方案，总的加油量最少呢？

其实最终影响总加油量的就两个条件：车辆百公里油耗 和 要求单次最短出租公里数。下面我们就分析这两个条件：

条件一：车辆百公里油耗

我们针对上面三辆车的油耗进行升序排列，即：奥迪A4L < 奔驰G < 法拉利。

条件二：单次最短出租公里数

我们我们针对上面三辆车的出租公里数进行升序排列，即：法拉利 < 奔驰G < 奥迪A4L。

确定好上面两个条件后，我们开始遍历有序的车辆百公里油耗。首先以最低油耗8L/公里为基准，只有奥迪A4L满足条件；再以最低油耗15L/公里为基准，奥迪A4L和奔驰G都满足条件；最后以最低油耗20L/公里为基准，三辆车都满足条件；由于我们只需要选择两辆车，此时则根据单次最短出租公里数为条件，选择该约束最小的两辆车即可。

四、代码实现

4.1> 采用Pair<Double, Pair<Integer, Integer>>封装worker信息

public class Solution {
    public double mincostToHireWorkers(int[] quality, int[] wage, int k) {
        Pair<Double, Pair<Integer, Integer>>[] workers = new Pair[quality.length];
        for (int i = 0; i < quality.length; i++) {
            workers[i] = new Pair((double) wage[i] / quality[i], new Pair(quality[i], wage[i]));
        }

        Arrays.sort(workers, (Pair<Double, Pair<Integer, Integer>> p1, Pair<Double, Pair<Integer, Integer>> p2) -> 
                p1.getKey() > p2.getKey() ? 1 : (p1.getKey() < p2.getKey() ? -1 : 0));
        PriorityQueue<Integer> pQueue = new PriorityQueue();
        double result = Integer.MAX_VALUE;
        int totalQuality = 0;
        for (Pair<Double, Pair<Integer, Integer>> worker : workers) {
            totalQuality = (totalQuality + worker.getValue().getKey());
            pQueue.add(-worker.getValue().getKey());
            if (pQueue.size() == k) {
                result = Math.min(result, (totalQuality * worker.getKey()));
                totalQuality += pQueue.poll();
            }
        }
        return result;
    }
} 

4.2> 采用Worker对象封装worker信息

public class Solution {
    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(quality[i], wage[i], (double) wage[i] / quality[i]);
        }

        // Arrays.sort(workers, Comparator.comparingDouble((Worker w) -> w.ratio));
        Arrays.sort(workers);
        PriorityQueue<Integer> pQueue = new PriorityQueue();
        double result = Integer.MAX_VALUE;
        int totalQuality = 0;
        for (Worker worker : workers) {
            totalQuality = (totalQuality + worker.quality);
            pQueue.add(-worker.quality);
            if (pQueue.size() == k) {
                result = Math.min(result, (totalQuality * worker.ratio));
                totalQuality += pQueue.poll();
            }
        }
        return result;
    }

    class Worker implements Comparable<Worker> {
        public int quality;
        public int wage;
        public double ratio;

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

        public int compareTo(Worker other) {
            return Double.compare(this.ratio, other.ratio);
        }
    }
}

今天的文章内容就这些了：

写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。

更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享，每天更新」