思路

1. 在最优发工资方案下，至少有一名工人，发给他的工资恰好等于他的最低期望工资。
2. 
3. 
   如何高效维护最小值？用最大堆。

class Solution:
    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:
        # 1. 计算每个工人单位工作效率所需工资的金钱
        # 2. 
        pairs = sorted( zip(quality, wage), key = lambda p: p[1]/p[0])

        # worker_set是候选的工人，默认是按照单位工作质量工资排序的前k个工人
        worker_heap = [ -q for q, _ in pairs[:k] ]
        heapify(worker_heap)
        sum_q = -sum(worker_heap)

        # 初始化以第k个工人的平均工资来计算
        ans = sum_q * pairs[k-1][4] / pairs[k-1][0]

        for q,w in pairs[k:]:
            if q < -worker_heap[0]:
                replace_q = heapreplace(worker_heap, -q)
                sum_q = sum_q + replace_q + q
                ans = min(ans, sum_q * (w/q))
        
        return ans

反思复盘：

1. 善用sorted函数和lambda表达式，快速构建有序元组列表，可以同时遍历多个列表及其比值。

2. 关于heapify最小堆的概念方法：

   https://blog.csdn.net/xiaomucgwlmx/article/details/103522410

3. heapify(heap)函数，将列表转化为最小堆。（想要最大堆就将列表元素取负）
4. heappush(heap, item)函数：将item添加到已有堆中，并自动保持堆的特性。
5. heappop(heap)：弹出并返回 heap 中的最小元素，保持剩余元素仍符合最小堆特性。
6. heapreplace(heap, item)：弹出堆中的最小元素，并将 item 加入堆中，是一步操作中完成的。这比单独先 heappop 然后 heappush 更高效，因为它只需要重新平衡一次堆。
7. heappushpop(heap, item)：先将 item 压入堆中，然后弹出并返回 heap 中的最小元素。这个操作与 heapreplace 相似，但顺序相反。