【leetcode】【2022/9/11】857. 雇佣 K 名工人的最低成本

问题描述：

• 有 n 名工人。给定两个数组 quality 和 wage，其中，quality[i] 表示第 i 名工人的工作质量，其最低期望工资为 wage[i]。
• 现在我们想雇佣 k 名工人组成一个工资组。在雇佣一组 k 名工人时，我们必须按照下述规则向他们支付工资：
  • 对工资组中的每名工人，应当按其工作质量与同组其他工人的工作质量的比例来支付工资。
  • 工资组中的每名工人至少应当得到他们的最低期望工资。
• 给定整数 k，返回组成满足上述条件的付费群体所需的最小金额。
  • 在实际答案的 10^{-5} 以内的答案将被接受。

核心思路：

• 该题没有思路，看了几个题解才明白，脑筋急转弯题。
  • 首先要清楚，选定 k 个人，如何使得所有人工资都满足期望值，同时工资总值最低？答案是按照员工工作的性价比，第 i 个人的性价比可以由 ratio[i] = wage[i]/quality[i] 得出，即每单位工作质量的工资。【注意 ratio[i] 越低，性价比越高】
  • 因此 k 个人一组，只需要以 ratio[i] 最高的工人作为基准即可满足条件；而假设这 k 名工人工资总和为 sum_q，则发的工资总额为 sum_q * ratio[i]。【即以最高标准给所有工人发工资，标准本身就是最低期望值】
  • 所以先将所有工人按照 ratio 排序（从小到大排序），接着再维护一个大小为 k 的最大堆即可确认选择的 k 个人选（堆中存放工人的工作质量）。
    • 具体来说，按照 ratio 从小到大的方式顺序遍历工人，当堆中已经有 k 个元素，而当前质量 quality[i] 低于堆顶质量，此时可以弹出堆顶，将 quality[i] 入堆。【因为此时访问的工人 ratio[i] 更高，此时只有更低的质量才有可能挤掉栈顶的工人】

代码实现：

• 代码实现如下：【代码参考自下面链接，没有变化，主要作了注释】

  class Solution
  {
  public:
      double mincostToHireWorkers(vector<int>& quality, vector<int>& wage, int k)
      {
          int m = quality.size();
          vector<int> id(m);
          iota(id.begin(), id.end(), 0); // 将数组 id 用 [0, m-1] 填充
          sort(id.begin(), id.end(), [&](const int& i, const int& j)
          {
              return wage[i] * quality[j] < wage[j] * quality[i]; // 判断 w[i]/q[i] < w[j]/q[j]
          });
  
          priority_queue<int> pq; // 优先队列默认为大根堆
          int sum_q = 0; // k 个工人的总质量
          for(int i = 0; i < k; ++i) pq.push(quality[id[i]]), sum_q += quality[id[i]];
          double ans = sum_q * ((double) wage[id[k-1]] / quality[id[k-1]]); // 选择 ratio 最小的 k 个工人一组
          for(int i = k; i < m; ++i) // 剩余工人
          {
              int q = quality[id[i]];
              if(q < pq.top()) // 此时 ratio 比前面的更大，因此总质量取更小值，才有可能有更优值
              {
                  sum_q -= pq.top(); sum_q += q; // 当前质量存入，弹出优先队列的最大质量
                  pq.pop(); pq.push(q);
                  ans = min(ans, sum_q * ((double) wage[id[i]] / q));
              }
          }
          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

参考内容：

• 一步步提示如何思考此题