雇佣 K 位工人的总代价 图解题解

这道题到底在问什么

输入

costs=[17,12,10,2,7,2,11,20,8], k=3, candidates=4

输出

11

最优解：一步一步想明白

1. 3记住「左右各取 candidates 个进最小堆 → 每轮弹堆顶最低 → 从弹出那侧补一个」,下面每一帧都在套它。
2. 4开局候选池是空的。左指针在最左 0、右指针在最右 8。先从左边连取 4 个工人放进最小堆。
3. 5从左边取下标 0 的工人(成本 17)放进候选池。左指针右移到 1。
4. 6从左边取下标 1 的工人(成本 12)放进候选池。左指针右移到 2。
5. 7从左边取下标 2 的工人(成本 10)放进候选池。左指针右移到 3。
6. 8从左边取下标 3 的工人(成本 2)放进候选池。左指针右移到 4。
7. 9从右边取下标 8 的工人(成本 8)放进候选池。右指针左移到 7。
8. 10从右边取下标 7 的工人(成本 20)放进候选池。右指针左移到 6。
9. 11从右边取下标 6 的工人(成本 11)放进候选池。右指针左移到 5。
10. 12从右边取下标 5 的工人(成本 2)放进候选池。右指针左移到 4。
11. 13候选池建好了,共 8 个候选;中间灰色那段还没进过池。每一轮就弹一次堆顶(成本最低、同成本下标小),开始雇人。
12. 14第 1 轮雇人:候选池里成本最低的是下标 3 的工人(成本 2、和另一个成本 2 并列,按下标小的先选),雇下他(绿色),总代价加到 2。他来自左侧。接下来按规则从左侧补一个新候选进池。
13. 15从左侧补一个:下标 4 的工人(成本 7)进池,候选池又回到 8 个,留给下一轮挑。
14. 16第 2 轮雇人:候选池里成本最低的是下标 5 的工人(成本 2),雇下他(绿色),总代价加到 4。他来自右侧。此时两端候选已取光(left=5 > right=4),不再补新人,后面直接从池里弹最低。
15. 17这时 left=5 已经越过 right=4,两端候选取光、没有新人可补,候选池剩 7 个,下一轮直接从池里弹最低。
16. 18第 3 轮雇人:候选池里成本最低的是下标 4 的工人(成本 7),雇下他(绿色),总代价加到 11。他来自左侧。这已是第 3 个、k 人凑满,算法到此停止、不再补人。
17. 19第 3 个人也雇好了,k 人已凑满,代码到这就停止,不会再雇了。此时 left=5 也已经越过 right=4,本就没有新人可补。
18. 20雇满 3 人,依次是成本 2、2、7,加起来最小总代价 11。靠「两端候选 + 最小堆 + 弹一个补一个」,每轮都全局取到当前能选的最低成本,不用反复扫整排。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import List
import heapq
class Solution:
    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:
        n = len(costs)
        heap = []
        left, right = 0, n - 1
        for _ in range(candidates):
            if left <= right:
                heapq.heappush(heap, (costs[left], left, 0))
                left += 1
        for _ in range(candidates):
            if left <= right:
                heapq.heappush(heap, (costs[right], right, 1))
                right -= 1
        ans = 0
        for _ in range(k):
            cost, idx, side = heapq.heappop(heap)
            ans += cost
            if left <= right:
                if side == 0:
                    heapq.heappush(heap, (costs[left], left, 0))
                    left += 1
                else:
                    heapq.heappush(heap, (costs[right], right, 1))
                    right -= 1
        return ans

#include <queue>
#include <tuple>
#include <vector>
using namespace std;
class Solution {
public:
    long long totalCost(vector<int>& costs, int k, int candidates) {
        using T = tuple<int,int,int>;
        priority_queue<T, vector<T>, greater<T>> pq;
        int n = costs.size(), left = 0, right = n - 1;
        for (int i = 0; i < candidates && left <= right; ++i) pq.push({costs[left], left++, 0});
        for (int i = 0; i < candidates && left <= right; ++i) pq.push({costs[right], right--, 1});
        long long ans = 0;
        while (k--) {
            auto [cost, idx, side] = pq.top(); pq.pop();
            ans += cost;
            if (left <= right) {
                if (side == 0) pq.push({costs[left], left++, 0});
                else pq.push({costs[right], right--, 1});
            }
        }
        return ans;
    }
};

import java.util.*;
class Solution {
    public long totalCost(int[] costs, int k, int candidates) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
        int left = 0, right = costs.length - 1;
        for (int i = 0; i < candidates && left <= right; i++) pq.offer(new int[]{costs[left], left++, 0});
        for (int i = 0; i < candidates && left <= right; i++) pq.offer(new int[]{costs[right], right--, 1});
        long ans = 0;
        while (k-- > 0) {
            int[] cur = pq.poll();
            ans += cur[0];
            if (left <= right) {
                if (cur[2] == 0) pq.offer(new int[]{costs[left], left++, 0});
                else pq.offer(new int[]{costs[right], right--, 1});
            }
        }
        return ans;
    }
}

复杂度

面试官可能追问