Hard

题目描述

有 n 名工人。给你两个整数数组 quality 和 wage，其中 quality[i] 是第 i 名工人的工作质量，wage[i] 是第 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 <= 10^4
  • 1 <= quality[i], wage[i] <= 10^4

解题思路

这道题的关键在于理解工资支付规则：工资必须与工作质量成正比，且每个工人都要满足最低期望工资。

核心思想：

  1. 设团队的工资比率为 ratio（每单位质量的工资），则每个工人的实际工资为 quality[i] * ratio
  2. 为满足最低期望，必须有 quality[i] * ratio >= wage[i]，即 ratio >= wage[i] / quality[i]
  3. 因此团队的工资比率必须 >= 所有成员的最低比率：ratio = max(wage[i] / quality[i]) 对所有成员 i

解法思路：

  1. 计算每个工人的最低比率 wage[i] / quality[i]，并按此比率排序
  2. 枚举每个工人作为"比率决定者"（即该工人的比率作为团队比率）
  3. 对于当前比率，我们只能选择比率不超过当前值的工人
  4. 在这些可选工人中，贪心地选择质量最小的 k 个工人（使用最大堆维护）
  5. 计算总成本：ratio * sum(selected_qualities)

使用优先队列（最大堆）来维护当前选中的 k 个工人的质量，当可选工人超过 k 个时，移除质量最大的工人。

代码实现

class Solution {
public:
    double mincostToHireWorkers(vector<int>& quality, vector<int>& wage, int k) {
        int n = quality.size();
        vector<pair<double, int>> workers;
        
        // 计算每个工人的最低比率
        for (int i = 0; i < n; i++) {
            workers.push_back({(double)wage[i] / quality[i], quality[i]});
        }
        
        // 按比率排序
        sort(workers.begin(), workers.end());
        
        priority_queue<int> pq; // 最大堆，存储质量
        int qualitySum = 0;
        double minCost = DBL_MAX;
        
        for (auto& worker : workers) {
            double ratio = worker.first;
            int qual = worker.second;
            
            pq.push(qual);
            qualitySum += qual;
            
            // 如果超过k个工人，移除质量最大的
            if (pq.size() > k) {
                qualitySum -= pq.top();
                pq.pop();
            }
            
            // 当达到k个工人时，计算成本
            if (pq.size() == k) {
                minCost = min(minCost, ratio * qualitySum);
            }
        }
        
        return minCost;
    }
};

class Solution:
    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:
        import heapq
        
        n = len(quality)
        workers = []
        
        # 计算每个工人的最低比率
        for i in range(n):
            workers.append((wage[i] / quality[i], quality[i]))
        
        # 按比率排序
        workers.sort()
        
        max_heap = []  # 最大堆，存储质量（使用负数模拟）
        quality_sum = 0
        min_cost = float('inf')
        
        for ratio, qual in workers:
            heapq.heappush(max_heap, -qual)  # 负数模拟最大堆
            quality_sum += qual
            
            # 如果超过k个工人，移除质量最大的
            if len(max_heap) > k:
                quality_sum += heapq.heappop(max_heap)  # 加负数等于减正数
            
            # 当达到k个工人时，计算成本
            if len(max_heap) == k:
                min_cost = min(min_cost, ratio * quality_sum)
        
        return min_cost

public class Solution {
    public double MincostToHireWorkers(int[] quality, int[] wage, int k) {
        int n = quality.Length;
        var workers = new List<(double ratio, int quality)>();
        
        // 计算每个工人的最低比率
        for (int i = 0; i < n; i++) {
            workers.Add(((double)wage[i] / quality[i], quality[i]));
        }
        
        // 按比率排序
        workers.Sort((a, b) => a.ratio.CompareTo(b.ratio));
        
        var maxHeap = new PriorityQueue<int, int>(Comparer<int>.Create((x, y) => y.CompareTo(x)));
        int qualitySum = 0;
        double minCost = double.MaxValue;
        
        foreach (var worker in workers) {
            double ratio = worker.ratio;
            int qual = worker.quality;
            
            maxHeap.Enqueue(qual, qual);
            qualitySum += qual;
            
            // 如果超过k个工人，移除质量最大的
            if (maxHeap.Count > k) {
                qualitySum -= maxHeap.Dequeue();
            }
            
            // 当达到k个工人时，计算成本
            if (maxHeap.Count == k) {
                minCost = Math.Min(minCost, ratio * qualitySum);
            }
        }
        
        return minCost;
    }
}

var mincostToHireWorkers = function(quality, wage, k) {
    const n = quality.length;
    const workers = [];
    
    for (let i = 0; i < n; i++) {
        workers.push({
            ratio: wage[i] / quality[i],
            quality: quality[i]
        });
    }
    
    workers.sort((a, b) => a.ratio - b.ratio);
    
    const maxHeap = [];
    let qualitySum = 0;
    let minCost = Infinity;
    
    for (let i = 0; i < n; i++) {
        maxHeap.push(workers[i].quality);
        qualitySum += workers[i].quality;
        
        maxHeap.sort((a, b) => b - a);
        
        if (maxHeap.length > k) {
            qualitySum -= maxHeap.shift();
        }
        
        if (maxHeap.length === k) {
            minCost = Math.min(minCost, qualitySum * workers[i].ratio);
        }
    }
    
    return minCost;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n log n)
空间复杂度O(n)

说明：

  • 时间复杂度：排序需要 O(n log n)，遍历每个工人并维护堆需要 O(n log k)，总体为 O(n log n)
  • 空间复杂度：存储工人信息和堆需要 O(n) 空间

相关题目