题目

有 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⁴
• 1 <= quality[i], wage[i] <= 10⁴

思路

优先队列

解法

class Solution {
    public double mincostToHireWorkers(int[] quality, int[] wage, int k) {
        int n = quality.length;
        // 用一个数组保存每名工人的情况，记录性价比。
        double[][] workers = new double[n][2];
        for (int i = 0; i < n; i++)
            workers[i] = new double[] {(double) wage[i] / quality[i], (double) quality[i]};
        // 注意保存的是预期工资和工作质量的比，越小性价比越高，
        // 按照第一个关键字升序排序。
        Arrays.sort(workers, (x, y) -> Double.compare(x[0], y[0]));
        double res = Double.MAX_VALUE;
        // 保存当前选中工人的工作质量总和。
        double sum = 0.0F;
        // 大顶堆保存当前选中的 k 个人的工作质量情况。
        PriorityQueue<Double> heap = new PriorityQueue<>((x, y) -> Double.compare(y, x));
        // 当前遍历到的是目前性价比最低的。
        for (double[] worker : workers) {
            // 如何计算 k 个人需要的最小工资？这样考虑，假设有三
            // 个工人 x1, x2, x3...，他们的质量是 q(x1),q(x2), 
            // q(x3)...，期望是 e(x1), e(x2), e(x3)...，实际分
            // 配的为 f(x1), f(x2), f(x3)..，有 q(x1)/f(x1) = 
            // q(x2)/f(x2) = q(x3)/f(x3) = ... = c，则对于所有
            // 的 xk，有 q(x)/c = f(x) >= e(x)，...，即 
            // q(x)/e(x) >= c，则要满足所有这样的，则要优先满足
            // q(x)/e(x) 最小的，即满足性价比最低的，也就是当前
            // 的 worker[0]，那么 worker[0] * sum 就可以满足所
            // 有的工人的最低需求了。
            if (heap.size() == k)
                // 如果当前已经安排了 k 个人，肯定先去掉质量最大
                // 的工人，来尽可能降低总质量（worker[0] * sum 
                // 是最低工资，既然 worker[0] 是定死的，那么想办
                // 法降低 sum，移除最大的）。
                sum -= heap.poll();
            // 先将当前性价比最低的工人加入。
            sum += worker[1];
            heap.offer(worker[1]);
            if (heap.size() == k)
                res = Math.min(res, sum * worker[0]);
        }
        return res;
    }
}

总结

• 分析出几种情况，然后分别对各个情况实现