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

题目

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

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

1、对工资组中的每名工人，应当按其工作质量与同组其他工人的工作质量的比例来支付工资。
2、工资组中的每名工人至少应当得到他们的最低期望工资。
给定整数 k ，返回 组成满足上述条件的付费群体所需的最小金额 。在实际答案的 10-5 以内的答案将被接受。。

示例

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

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/minimum-cost-to-hire-k-workers
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方法1：贪心+优先队列

题解：https://leetcode.cn/problems/minimum-cost-to-hire-k-workers/solution/ji-yao-jie-ge-di-you-yao-shu-liang-shao-r0lj9/

Java实现

class Solution {
    public double mincostToHireWorkers(int[] quality, int[] wage, int k) {
        int n = quality.length;
        //存放下标
        Integer[] flag = new Integer[n];
        for (int i = 0; i < n; i++) flag[i] = i;
        
        //将下标，按照单位价格升序排序。（不用除法用交叉相乘）
        Arrays.sort(flag, (a, b) -> {
            return wage[a] * quality[b] - wage[b] * quality[a];
        });

        //声明大根堆
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> {
            return b - a;
        });

        //price记录当前价格，cnt记录劳动量
        double price = 0, cnt = 0, ans = Double.MAX_VALUE;

        for (int i = 0; i < n; i++) {
            if (pq.size() < k) {
                cnt += quality[flag[i]];
                price = (double)wage[flag[i]] / quality[flag[i]];
                pq.offer(quality[flag[i]]);
            } else if (quality[flag[i]] < pq.peek()) {
                cnt -= pq.peek() - quality[flag[i]];
                price = (double)wage[flag[i]] / quality[flag[i]];
                pq.poll();
                pq.offer(quality[flag[i]]);
            }

            if (pq.size() == k) {
                ans = Math.min(ans, price * cnt);
            }
        }
        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
36
37
38
39