title
有 N 名工人。 第 i 名工人的工作质量为 quality[i] ，其最低期望工资为 wage[i] 。
现在我们想雇佣 K 名工人组成一个工资组。在雇佣 一组 K 名工人时，我们必须按照下述规则向他们支付工资：
- 对工资组中的每名工人，应当按其工作质量与同组其他工人的工作质量的比例来支付工资。
- 工资组中的每名工人至少应当得到他们的最低期望工资。
返回组成一个满足上述条件的工资组至少需要多少钱。
示例 1：
输入： quality = [10,20,5], wage = [70,50,30], K = 2
输出： 105.00000
解释： 我们向 0 号工人支付 70，向 2 号工人支付 35。
示例 2：
输入： quality = [3,1,10,10,1], wage = [4,8,2,2,7], K = 3
输出： 30.66667
解释： 我们向 0 号工人支付 4，向 2 号和 3 号分别支付 13.33333。
提示：
1 <= K <= N <= 10000，其中N = quality.length = wage.length1 <= quality[i] <= 100001 <= wage[i] <= 10000- 与正确答案误差在
10^-5之内的答案将被视为正确的。
solution
按工作价值排序，然后当每个为最大工作价值时，从前i-1个里求K-1个凑成k个
class Solution:
def mincostToHireWorkers(self, quality: List[int], wage: List[int], K: int) -> float:
from heapq import heappush, heappop, heappushpop
hq = []
n = len(quality)
if n < K:
return 0
data = [(w / q, q, w) for q, w in zip(quality, wage)]
data = sorted(data, key=lambda x: x[0])
ans = float('inf')
sumq = 0
for ratio, q, w in data:
# 维护大顶堆，找当前item之前里的K-1个元素，再加当前的就正好K个了
if len(hq) > K - 1:
sumq += heappop(hq)
if len(hq) == K - 1:
ans = min(ans, (sumq + q) * ratio)
heappush(hq, -q)
sumq += q
return ans