2462. 雇佣 K 名工人的总代价

Medium

题目描述

给你一个下标从 0 开始的整数数组 costs ，其中 costs[i] 是雇佣第 i 名工人的代价。

同时给你两个整数 k 和 candidates 。我们想根据以下规则恰好雇佣 k 名工人：

总共进行 k 轮雇佣，每一轮恰好雇佣一名工人。
在每一轮雇佣中，从最前面 candidates 名工人和最后面 candidates 名工人中选出代价最小的一名工人，两者中代价相同时，选择下标更小的一名工人。
- 比如，costs = [3,2,7,7,1,2] 且 candidates = 2 ，第一轮雇佣中，我们选择第 4 名工人，因为他的代价最小 [3,2,7,7,1,2] 。
- 第二轮雇佣，我们选择第 1 名工人，因为他们的代价与第 4 名工人一样都是最小代价，而且下标更小，[3,2,7,7,2] 。注意每一轮雇佣后，剩余工人的下标可能会发生变化。
如果剩余员工数目不足 candidates 人，那么下一轮雇佣就在剩余的工人中选。

返回雇佣恰好 k 名工人的总代价。

示例 1：

输入：costs = [17,12,10,2,7,2,11,20,8], k = 3, candidates = 4
输出：11
解释：我们总共雇佣 3 名工人。总代价一开始是 0 。
- 第一轮雇佣，我们从 [17,12,10,2,7,2,11,20,8] 中选择。最小代价是 2 ，有两个下标：3 和 5 。我们选择下标更小的 3 。总代价是 0 + 2 = 2 。
- 第二轮雇佣，我们从 [17,12,10,7,2,11,20,8] 中选择。最小代价是 2 ，下标为 4 。总代价是 2 + 2 = 4 。
- 第三轮雇佣，我们从 [17,12,10,7,11,20,8] 中选择。最小代价是 7 ，下标为 3 。总代价是 4 + 7 = 11 。注意下标为 3 的工人同时在最前面 4 名工人和最后面 4 名工人中。
总雇佣代价是 11 。

示例 2：

输入：costs = [1,2,4,1], k = 3, candidates = 3
输出：4
解释：我们总共雇佣 3 名工人。总代价一开始是 0 。
- 第一轮雇佣，我们从 [1,2,4,1] 中选择。最小代价是 1 ，有两个下标：0 和 3 。我们选择下标更小的 0 。总代价是 0 + 1 = 1 。注意下标 1 和 2 的工人同时在最前面 3 名工人和最后面 3 名工人中。
- 第二轮雇佣，我们从 [2,4,1] 中选择。最小代价是 1 ，下标为 2 。总代价是 1 + 1 = 2 。
- 第三轮雇佣，少于 3 名工人，我们从剩余工人 [2,4] 中选择。最小代价是 2 ，下标为 0 。总代价是 2 + 2 = 4 。
总雇佣代价是 4 。

提示：

1 <= costs.length <= 10^5
1 <= costs[i] <= 10^5
1 <= k, candidates <= costs.length

解题思路

这道题需要模拟雇佣过程，关键在于每次都要从候选工人中选择代价最小的那一个。

核心思路： 使用双堆（优先队列）来高效维护左右两端的候选工人：

左堆：存储从数组开头开始的 candidates 个工人
右堆：存储从数组末尾开始的 candidates 个工人
为了处理平局（代价相同时选择下标更小的），我们在堆中存储 (cost, index) 对

具体步骤：

初始化左右两个最小堆，分别放入数组前 candidates 个和后 candidates 个元素
使用两个指针 left 和 right 标记当前左右两端已经加入堆的边界
重复 k 次雇佣过程：
- 比较两个堆的堆顶元素，选择代价更小的（平局时选下标更小的）
- 将选中的工人代价累加到总代价中
- 从对应堆中移除该工人
- 如果还有未加入堆的工人，将下一个工人加入对应的堆中

优化细节：

当 left > right 时，说明所有工人都已经在候选范围内，此时只需要从一个全局堆中选择即可
注意边界处理，避免重复添加同一个工人

代码实现

class Solution {
public:
    long long totalCost(vector<int>& costs, int k, int candidates) {
        int n = costs.size();
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> leftHeap, rightHeap;
        
        int left = 0, right = n - 1;
        
        // 初始化左堆
        for (int i = 0; i < candidates && left <= right; i++) {
            leftHeap.push({costs[left], left});
            left++;
        }
        
        // 初始化右堆
        for (int i = 0; i < candidates && left <= right; i++) {
            rightHeap.push({costs[right], right});
            right--;
        }
        
        long long totalCost = 0;
        
        for (int i = 0; i < k; i++) {
            if (leftHeap.empty()) {
                totalCost += rightHeap.top().first;
                rightHeap.pop();
                if (left <= right) {
                    rightHeap.push({costs[right], right});
                    right--;
                }
            } else if (rightHeap.empty()) {
                totalCost += leftHeap.top().first;
                leftHeap.pop();
                if (left <= right) {
                    leftHeap.push({costs[left], left});
                    left++;
                }
            } else if (leftHeap.top() <= rightHeap.top()) {
                totalCost += leftHeap.top().first;
                leftHeap.pop();
                if (left <= right) {
                    leftHeap.push({costs[left], left});
                    left++;
                }
            } else {
                totalCost += rightHeap.top().first;
                rightHeap.pop();
                if (left <= right) {
                    rightHeap.push({costs[right], right});
                    right--;
                }
            }
        }
        
        return totalCost;
    }
};

class Solution:
    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:
        import heapq
        
        n = len(costs)
        left_heap = []
        right_heap = []
        
        left, right = 0, n - 1
        
        # 初始化左堆
        for _ in range(candidates):
            if left <= right:
                heapq.heappush(left_heap, (costs[left], left))
                left += 1
        
        # 初始化右堆
        for _ in range(candidates):
            if left <= right:
                heapq.heappush(right_heap, (costs[right], right))
                right -= 1
        
        total_cost = 0
        
        for _ in range(k):
            if not left_heap:
                cost, idx = heapq.heappop(right_heap)
                total_cost += cost
                if left <= right:
                    heapq.heappush(right_heap, (costs[right], right))
                    right -= 1
            elif not right_heap:
                cost, idx = heapq.heappop(left_heap)
                total_cost += cost
                if left <= right:
                    heapq.heappush(left_heap, (costs[left], left))
                    left += 1
            elif left_heap[0] <= right_heap[0]:
                cost, idx = heapq.heappop(left_heap)
                total_cost += cost
                if left <= right:
                    heapq.heappush(left_heap, (costs[left], left))
                    left += 1
            else:
                cost, idx = heapq.heappop(right_heap)
                total_cost += cost
                if left <= right:
                    heapq.heappush(right_heap, (costs[right], right))
                    right -= 1
        
        return total_cost

public class Solution {
    public long TotalCost(int[] costs, int k, int candidates) {
        int n = costs.Length;
        var leftHeap = new PriorityQueue<(int cost, int index), (int cost, int index)>();
        var rightHeap = new PriorityQueue<(int cost, int index), (int cost, int index)>();
        
        int left = 0, right = n - 1;
        
        // 初始化左堆
        for (int i = 0; i < candidates && left <= right; i++) {
            leftHeap.Enqueue((costs[left], left), (costs[left], left));
            left++;
        }
        
        // 初始化右堆
        for (int i = 0; i < candidates && left <= right; i++) {
            rightHeap.Enqueue((costs[right], right), (costs[right], right));
            right--;
        }
        
        long totalCost = 0;
        
        for (int i = 0; i < k; i++) {
            if (leftHeap.Count == 0) {
                var (cost, idx) = rightHeap.Dequeue();
                totalCost += cost;
                if (left <= right) {
                    rightHeap.Enqueue((costs[right], right), (costs[right], right));
                    right--;
                }
            } else if (rightHeap.Count == 0) {
                var (cost, idx) = leftHeap.Dequeue();
                totalCost += cost;
                if (left <= right) {
                    leftHeap.Enqueue((costs[left], left), (costs[left], left));
                    left++;
                }
            } else {
                var leftTop = leftHeap.Peek();
                var rightTop = rightHeap.Peek();
                if (leftTop.cost < rightTop.cost || (leftTop.cost == rightTop.cost && leftTop.index < rightTop.index)) {
                    totalCost += leftTop.cost;
                    leftHeap.Dequeue();
                    if (left <= right) {
                        leftHeap.Enqueue((costs[left], left), (costs[left], left));
                        left++;
                    }
                } else {
                    totalCost += rightTop.cost;
                    rightHeap.Dequeue();
                    if (left <= right) {
                        rightHeap.Enqueue((costs[right], right), (costs[right], right));
                        right--;
                    }
                }
            }
        }
        
        return totalCost;
    }
}

var totalCost = function(costs, k, candidates) {
    const leftHeap = new MinPriorityQueue({ priority: x => x.cost * 100000 + x.index });
    const rightHeap = new MinPriorityQueue({ priority: x => x.cost * 100000 + x.index });
    
    let left = 0;
    let right = costs.length - 1;
    let totalCost = 0;
    
    // Initialize heaps
    for (let i = 0; i < candidates && left <= right; i++) {
        leftHeap.enqueue({ cost: costs[left], index: left });
        left++;
    }
    
    for (let i = 0; i < candidates && left <= right; i++) {
        rightHeap.enqueue({ cost: costs[right], index: right });
        right--;
    }
    
    for (let i = 0; i < k; i++) {
        const leftMin = leftHeap.isEmpty() ? null : leftHeap.front().element;
        const rightMin = rightHeap.isEmpty() ? null : rightHeap.front().element;
        
        let chosen;
        if (!leftMin) {
            chosen = rightHeap.dequeue().element;
        } else if (!rightMin) {
            chosen = leftHeap.dequeue().element;
        } else if (leftMin.cost < rightMin.cost || (leftMin.cost === rightMin.cost && leftMin.index < rightMin.index)) {
            chosen = leftHeap.dequeue().element;
        } else {
            chosen = rightHeap.dequeue().element;
        }
        
        totalCost += chosen.cost;
        
        // Add new candidate if available
        if (left <= right) {
            if (leftHeap.isEmpty() || (!rightHeap.isEmpty() && chosen.index < costs.length / 2)) {
                leftHeap.enqueue({ cost: costs[left], index: left });
                left++;
            } else {
                rightHeap.enqueue({ cost: costs[right], index: right });
                right--;
            }
        }
    }
    
    return totalCost;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	复杂度	说明
时间复杂度	O(k log candidates)	需要进行 k 次雇佣，每次从堆中取出和插入元素的时间复杂度为 O(log candidates)
空间复杂度

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目