.雇佣 K 名工人的最低成本（java，算法）
.雇佣 K 名工人的最低成本
有 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。
思路和注释都在代码块里面了
放张图缓解一下眼疲劳，嘿嘿
package cn.itcast.algorithm.TTT_78; import java.util.Arrays; import java.util.PriorityQueue; public class Main81 { public static void main(String[] args) { /** * 测试用例 */ int [] quality = {10,20,5}; //工作质量 int[] wage = {70,50,30}; //最低期望工资 int k = 2; //租用的工人数 /** * 实现方法mincostToHireWorkers */ double sum = mincostToHireWorkers(quality,wage,k); System.out.println(sum); } /* (一)每个工人都有自己期望的价性比，雇佣K个工人的时候要满足 每个人的实际价性比不低于他的期望， 即需要按照K个工人中的最高期望价性比给这K个人开工资。 (二)使用了一个大根堆，来获取K个工人的最大的价性比， 作为K个工人的价性比，使用qsum保存K个工人的质量和。 要给他们付的工资就是qsum * 最大性价比。 */ private static double mincostToHireWorkers(int[] quality, int[] wage, int k) { double[][] workers = new double[quality.length][2]; for (int i = 0; i < quality.length; ++i){//保存工人价性比 workers[i] = new double[]{(double)(wage[i]) / quality[i], (double)quality[i]}; } Arrays.sort(workers, (a, b) -> Double.compare(a[0], b[0])); double qian = Double.MAX_VALUE; double qsum = 0.0; //qsum保存K个工人的质量和 PriorityQueue<Double> pq = new PriorityQueue<>(); for (double[] worker: workers) { qsum += worker[1]; pq.add(-worker[1]); if (pq.size() > k) { qsum += pq.poll(); } if (pq.size() == k) { qian = Math.min(qian, qsum * worker[0]); } } return qian; } }
