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

给你一个下标从 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 位工人的总代价。

java

1
2
3
4
5
6
7
8输入：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 位工人。总代价是 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 位工人中。
总雇佣代价是 11 。

java

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

解：

这一题的的一个巧妙的解法是使用优先队列 PriorityQueue 题目中描述先按照工价进行比较，工价相同选择序号小的，所以定义右下队列：工价不同时比较工价，工价相同时比较序号

java

PriorityQueue<int[] > pq = new PriorityQueue<>((a, b) -> a[0] != b[0] : a[0] - b[0] ? a[1] - b[1]);

因为题目要求，是从前后 candidates 个元素中来选择工价最低的，所以呢我们使用双指针来

java

1
2
3
4int n = costs.length;
int left = candidates -1；//左候选区的最后一个
int right = n - candidates ；//右候选区的第一个

之后我们便是向优先队列里插元素

java

1
2
3
4
5
6
7for(int i = 0; i <= left; i++){
	pd.offer(new int[]{costs[i],i});
}
for(int i = right; i <= n; i++){
	pd.offer(new int[]{costs[i},i});
}

但是呢题目给出了这样了这样一句话((20250217183727-2l50bvy "如果剩余员工数目不足 candidates 人，那么下一轮雇佣他们中代价最小的一人，如果有多位代价相同且最小的工人，选择下标更小的一位工人。"))所以我们需要考虑额外情况，翻译成我们的代码就是 left +1 ≥ right(或者 candidats*2 >= n）时怎么办?

java

1
2
3
4for (int i = 0; i < n; ++i) {
	pq.offer(new int[]{costs[i], i});
}

优先队列插入元素后，我们就可以进行挑选出代价最小的工人了因为是优先队列，所以直接取出，代价最小的工人

唯一注意的是，我们挑选出的代价最小的工人后，人数会-1，所以候选区会改变

我们需要判断工人是来自左边的候选区还是右边的候选区，如果是左边的候选区，我们的 left 就要 +1 如果是右边的候选区，我们的 right 就要-1 以此保证候选区内人数不变

如果候选区重叠，则不用管，因为已经没有可插入的元素了

java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 long top = 0;
        for(int i = 0; i < k; i++){
            int [] min = pd.poll();
            int cost = min[0];
            int id = min[1];
            top += cost;

            if(left + 1 < right){
                if(id <= left){
                    left++;
                    pd.offer(new int[]{costs[left], left});
                }else{
                    right--;
                    pd.offer(new int[]{costs[right], right});
                }
            }
        }

java

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
31
32
33
34
35
36
37
38
39
40
41class Solution {
    public long totalCost(int[] costs, int k, int candidates) {
        PriorityQueue<int[] > pd = new PriorityQueue<>( (a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
        int n = costs.length;
        int left = candidates - 1;
        int right = n - candidates;
        if(candidates * 2 < n){
            for(int i = 0; i <= left; i++){
                pd.offer(new int[]{costs[i],i});
            }
            for(int i = right; i < n; i++){
                pd.offer(new int[]{costs[i],i});
            }
        }else{
            for(int i = 0; i < n; i++){
                pd.offer(new int[]{costs[i],i});
            }
        }

        //弹出
        long top = 0;
        for(int i = 0; i < k; i++){
            int [] min = pd.poll();
            int cost = min[0];
            int id = min[1];
            top += cost;

            if(left + 1 < right){
                if(id <= left){
                    left++;
                    pd.offer(new int[]{costs[left], left});
                }else{
                    right--;
                    pd.offer(new int[]{costs[right], right});
                }
            }
        }
        return top;
    }
}

力扣2462. 雇佣 K 位工人的总代价

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

评论 (0)

还没有评论