初学python记录：力扣2462. 雇佣 K 位工人的总代价

本文主要是介绍初学python记录：力扣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 位工人的总代价。

提示：

1 <= costs.length <= 105
1 <= costs[i] <= 105
1 <= k, candidates <= costs.length

思考：

暴力解法

招k个人即为k次循环，每次判断待选人与candidates的大小关系，选出题意所需的最小花销和员工索引，从待选人中去掉该员工，进行下一次循环。每次花销相加即为结果，代码如下：

class Solution(object):def totalCost(self, costs, k, candidates):""":type costs: List[int]:type k: int:type candidates: int:rtype: int"""n = len(costs)ans = 0for _ in range(k):if n < candidates:# 如果剩余员工数目不足 candidates 人，那么下一轮雇佣他们中代价最小的一人，如果有多位代价相同且最小的工人，选择下标更小的一位工人。min_value = min(costs)index = costs.index(min_value)ans += min_valuecosts.pop(index)n -= 1else:# 在每一轮雇佣中，从最前面 candidates 和最后面 candidates 人中选出代价最小的一位工人，如果有多位代价相同且最小的工人，选择下标更小的一位工人。min_value = 10 ** 6for i in range(candidates):if costs[i] < min_value:min_value = costs[i]index = ifor j in range(n - candidates, n):if costs[j] < min_value:min_value = costs[j]index = jans += min_valuecosts.pop(index)n -= 1return ans

提交超时，卡在第 132 / 162 个例子：

优化——最小堆

1. 设n为costs数组的长度（即候选人数量），若n - candidates*2 < k，则我们选取的k个人一定是整个costs数组中最小的k个数，所以直接返回最小的k个数的和即可；

2. 否则，分别用两个最小堆储存 前candidates个元素 和 后candidates个元素，每次比较两个最小堆的堆顶元素，选更小的从堆顶弹出并加到ans，并向堆中填充对应位置的新元素。直到选完k个人为止。

代码如下：

class Solution(object):def totalCost(self, costs, k, candidates):""":type costs: List[int]:type k: int:type candidates: int:rtype: int"""n = len(costs)    # 待选人数量ans = 0if n < candidates*2 + k:costs.sort()return sum(costs[:k])wait_1 = costs[:candidates]     # 前candidates个元素wait_2 = costs[-candidates:]     # 后candidates个元素# 转成最小堆的形式heapify(wait_1)heapify(wait_2)left = candidatesright = n - 1 - candidatesfor _ in range(k):# 比较两个最小堆堆顶元素，选更小的弹出并加到ans，并向堆中填充对应位置的新元素if wait_1[0] <= wait_2[0]:ans += heapreplace(wait_1, costs[left])left += 1else:ans += heapreplace(wait_2, costs[right])right -= 1return ans

提交通过：