带你读《图解算法小抄》二十二、贪心算法（10）

带你读《图解算法小抄》二十二、贪心算法（9）https://developer.aliyun.com/article/1347844?groupCode=tech_library

3）实现

注意：根据题目的描述，假设你总是可以到达数组的最后一个位置，因此无需考虑无法到达末尾的情况。

以上就是使用贪心算法解决跳跃游戏 II 问题的详细步骤和算法框架。该算法具有时间复杂度 O(n)，其中 n 是数组的长度。

14.雇用K名工人的最低成本

1）题目描述

有一组工人，每个工人的工作质量为 quality[i]，期望的最低工资为 wage[i]。现在需要雇佣 K 名工人来完成一项工作。其中，每名工人只能接受与其工作质量相同或更高的工资。求解需要满足工人数量为 K 的情况下，所需的最小总工资。

2）解题步骤

为了解决最小成本雇佣工人的问题，我们可以使用贪心算法来解决。贪心算法的思路是优先选择工资效益最高的工人。

我们按照以下步骤进行解题：

• 创建一个数组 ratios[]，用于存储每个工人的工资与工作质量的比率（wage[i]/quality[i]）。
  
• 将工人按照 ratios[] 的升序进行排序，以便能够从低比率到高比率依次选择工人。
  
• 创建一个最小堆 pq，用于维护当前选择的 K 名工人的最高工资。
  
• 初始化变量 sumQuality 为 0，用于累计当前选择的工人的工作质量之和。
  
• 遍历排序后的工人列表，对于每个工人：
  
• 将其加入堆 pq。
  
• 将其工作质量添加到 sumQuality。
  
• 如果堆 pq 中的工人数量超过 K，则移除堆顶的工人（即最高工资的工人）。
  
• 如果堆 pq 中的工人数量等于 K，计算当前总工资 currWage，即当前选择的 K 名工人中的最高工资乘以 sumQuality。
  
• 如果 currWage 小于当前的最小总工资 minWage，更新 minWage 的值。
  

• 遍历结束后，minWage 就是所需的最小总工资。
  

以下是使用贪心算法解决最小成本雇佣工人问题的算法框架：

function mincostToHireWorkers(quality, wage, K) {
  const workers = [];
  const n = quality.length;  for (let i = 0; i < n; i++) {
    const ratio = wage[i] / quality[i];
    workers.push([quality[i], wage[i], ratio]);
  }  workers.sort((a, b) => a[2] - b[2]);  let sumQuality = 0;
  let minWage = Infinity;
  const pq = new MaxHeap();  for (let i = 0; i < n; i++) {
    const [currQuality, currWage, ratio] = workers[i];    pq.insert(currQuality);
    sumQuality += currQuality;    if (pq.size() > K) {
      sumQuality -= pq.extractMax();
    }    if (pq.size() === K) {
      const currWageSum = sumQuality * ratio;
      minWage = Math.min(minWage, currWageSum);
    }
  }
  return minWage;
}