日期: 2024 年 5 月 2 日

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

思路

从quality中选k个，按照工作质量比例支付工资，并且每人的工资不能低于wage中的最低期望工资，问雇佣这k个人的最低成本是多少。

// todo

代码

/**
 * @date 2024-05-02 20:44
 */
public class MincostToHireWorkers857 {
    public double mincostToHireWorkers(int[] quality, int[] wage, int k) {
        int n = wage.length;
        PriorityQueue<double[]> wqq = new PriorityQueue<>(Comparator.comparingDouble(x -> x[0]));
        double[][] wq = new double[n][2];
        for (int i = 0; i < wage.length; i++) {
            wq[i][0] = (double) wage[i] / quality[i];
            wq[i][1] = i;
            wqq.offer(wq[i]);
        }
        PriorityQueue<Integer> q = new PriorityQueue<>((x, y) -> y - x);
        int sum = 0;
        int ri = 0;
        for (int i = 0; i < k; i++) {
            double[] choose = wqq.poll();
            int index = (int) choose[1];
            sum += quality[index];
            q.offer(quality[index]);
            ri = (int) choose[1];
        }
        double res = (double) sum * wage[ri] / quality[ri];
        while (!wqq.isEmpty()) {
            double[] choose = wqq.poll();
            int index = (int) choose[1];
            if (q.peek() > quality[index]) {
                sum = sum - q.peek() + quality[index];
                double resTmp = (double)sum * wage[index] / quality[index];
                q.poll();
                q.offer(quality[index]);
                if (res > resTmp) {
                    res = resTmp;
                }
            }
        }
        return res;
    }
}

性能