雇用K个工人测试用例失败

Question

问题

给定一个 0 索引的整数数组 cost，其中 cost[i] 是雇用第 i 个工人的成本。 您还将获得两个整数 k 和候选数。我们想根据以下规则雇用恰好 k 个工人：

• 您将运行 k 个会话，并在每个会话中仅雇用一名工人。
• 每次招聘时，从第一批候选员工或最后一批候选员工中选择成本最低的员工。以最小的指数打破平局。
• 如果剩下的候选工人少于候选工人，则选择其中成本最低的工人。以最小的指数打破平局。

一个工人只能被选择一次。 返回雇用恰好 k 个工人的总成本。

问题链接

逻辑

有两个最小堆，左边一个，右边一个。

• 从两个堆中弹出并比较它们。如果左边的元素更大，则从左边输入一个新添加的元素，然后将右边的元素推回到堆中
• 如果右侧的元素更大，则将数组中的一个新元素添加到右侧堆，将左侧的元素推回到左侧堆，因为它失去了平局
• 继续将工人的成本添加到

  total_cost

  变量中作为回报

  total_cost

代码

import heapq
from typing import List

class Solution:
    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:
        left_h = []
        right_h = []
        N = len(costs)
        total_cost = 0
        left_idx = candidates - 1
        right_idx = N - candidates

        for i in range(candidates):
            heapq.heappush(left_h, costs[i])

        for i in range(right_idx, N):
            heapq.heappush(right_h, costs[i])

        i = 0
        while i < k:
            left_ele = heapq.heappop(left_h)
            right_ele = heapq.heappop(right_h)
            if left_ele <= right_ele:
                total_cost += left_ele
                heapq.heappush(right_h, right_ele)
                if left_idx + 1 < N and (right_idx == N or left_idx + 1 < right_idx):
                    heapq.heappush(left_h, costs[left_idx + 1])
                    left_idx += 1
            else:
                total_cost += right_ele
                heapq.heappush(left_h, left_ele)
                if right_idx - 1 >= 0 and (left_idx == -1 or right_idx - 1 > left_idx):
                    heapq.heappush(right_h, costs[right_idx - 1])
                    right_idx -= 1
            i += 1
        return total_cost

solution = Solution()
costs = [28,35,21,13,21,72,35,52,74,92,25,65,77,1,73,32,43,68,8,100,84,80,14,88,42,53,98,69,64,40,60,23,99,83,5,21,76,34]
k = 32
candidates = 12
print(solution.totalCost(costs, k, candidates))  # Output: 1407 # Expected: 1407

costs = [18,64,12,21,21,78,36,58,88,58,99,26,92,91,53,10,24,25,20,92,73,63,51,65,87,6,17,32,14,42,46,65,43,9,75]
k = 13
candidates = 23
print(solution.totalCost(costs, k, candidates))  # Output: 202  # Expected: 223

问题

程序中给出的情况失败了。

Answer 1

left_idx

是左侧最后插入的项目的索引。

right_idx

是右侧最后插入的项目的索引。

如果您运行程序，

left_idx=21

和

right_idx=21

，那么您已将相同的项目插入到两个堆中。

将

left_idx < right_idx

更改为

left_idx + 1 < right_idx

。