题目描述

leetcode857. 雇佣 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 <= 104
  • 1 <= quality[i], wage[i] <= 104

题解——既要价格低，又要数量少

理解题意

我们可以将quality[i]视为每个工人的劳动，而wage[i]/quality[i]视为一单位劳动的价格。这样，就可以理解为：按照所有工人中最贵的价格，向每个工人按劳支付工资。那么，要使总花费最少，就要从两个方面入手：尽可能选用单位价格低的工人，以及使k个工人总劳动量尽量少。

思路

如果我们将每个工人按照单位价格升序排列，再依次添加，就保证了真正价格(最大价格)就是最后添加的那个价格。同时，维护一个定长为k的优先队列，存放前面的劳动量最少的k个值，并维护它们的和。这样，相当于找到了真正价格为k时的局部最优(劳动和最小)。那么，从头遍历一遍(相当于遍历所有的价格)，就尝试了所有可能的答案。

此外，为了避免两次排序，另设一个flag数组，存放下标，再用lambda表达式对下标排序。

代码

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
class Solution {
public:
    double mincostToHireWorkers(vector<int>& quality, vector<int>& wage, int k) {
        vector<int> flag;//存放下标
        int sz=quality.size();
        for(int i=0;i<sz;++i) flag.push_back(i);//将下标存入，按照价格升序排列(使用交叉相乘而不是除法)
        sort(flag.begin(),flag.end(),[&](int a,int b){return wage[a]*quality[b]<wage[b]*quality[a];});
        priority_queue<int> pq;//优先队列(大顶堆)
        double price,cnt=0,ans=INT_MAX;//price记录当前价格，cnt记录劳动量
        for(int i=0;i<sz;++i)//按照flag中的顺序进行遍历
        {
            if(pq.size()<k)//还没有达到k时，直接添加并记录价格
            {
                cnt+=quality[flag[i]];
                price=wage[flag[i]]*1.0/quality[flag[i]];//注意*1.0，转化为double
                pq.push(quality[flag[i]]);
            }
            else if(quality[flag[i]]<pq.top()) //达到k后，只有当数量比最大的小时，才可能更优，存入
            {
                cnt-=pq.top()-quality[flag[i]];
                price=wage[flag[i]]*1.0/quality[flag[i]];
                pq.pop();
                pq.push(quality[flag[i]]);
            }
            if(pq.size()==k)//计算答案并对比
                ans=min(ans,price*cnt);
        }
        return ans;
    }
};