857. 雇佣 K 名工人的最低成本：最大堆

题目描述

这是 力扣上的 857. 雇佣 K 名工人的最低成本，难度为 困难。

有 n 名工人。 给定两个数组 quality 和 wage ，其中，quality[i] 表示第 i 名工人的工作质量，其最低期望工资为 wage[i] 。

现在我们想雇佣 k 名工人组成一个工资组。在雇佣 一组 k 名工人时，我们必须按照下述规则向他们支付工资：

对工资组中的每名工人，应当按其工作质量与同组其他工人的工作质量的比例来支付工资。

工资组中的每名工人至少应当得到他们的最低期望工资。

给定整数 k ，返回 组成满足上述条件的付费群体所需的最小金额 。在实际答案的 10-5 以内的答案将被接受。。

题目分析

仔细看看题目我们可以知道，给工人发工资都是有标准的，那就是会按照某一个人的期望薪资/工作质量，的到的单位质量薪资，来作为其他人的单位薪资

那么其实我们就可以知道，给 k 个人发工资，那么至少是有 1 个人得到的工资是自己所期望的工资，其他人得到的工资会是比期望的工资多或者正好相等，因此我们可以从找这个第 k 个人开始思考

在这里，我们知道单位质量薪资可以这么算：

ri=wagei/qualityir_i = wage_i/quality_iri=wagei/qualityi此处的 i 代表每一个工人的下标

这个时候，咱们要进行选择的话，自然是要对每一个工人的单位质量薪资进行一次排序（从小到大） ，当我们确定以某一个rir_iri为基准工资的时候，实际上我们知道 i 前面的工人，都是可以选择的，因为他们的quality∗ri必定是>=wageiquality * r_i 必定是 >= wage_iquality∗ri必定是>=wagei的，（因为定义的基准rir_iri是大于他们的 ）

那么根据题意，是需要我们使用最小的成本来招 k 个人，那么我们到底要如何找对应的 k 个工人呢？

目前我们还不知道到底基准的 rir_iri 是多少，但是我们可以找关系，关系很重要

K 个人的质量和为可以设为 sumQ，基准单位质量薪资为rir_iri，那么他们的成本是sumQ∗risumQ*r_isumQ∗ri，通过这个式子我们可以知道，当rir_iri确定的时候，sumQ 尽可能的小，最终的成本才会是最小的

最后

我们去找 k 个员工的时候，实际上我们是在比那里排序后的单位质量薪资数组过程中去维护一个最大堆，首先先将前 k 个员工的 quality 放进最大堆，然后在遍历 k 后面的员工的 quality 是否会小于最大堆的对顶，若是，则咱们可以替换堆顶，因为此时 sumQ 可以变小，那么最终的成本是有机会变低的

最终再计算是否需要我们更新最低的成本即可，遍历完毕之后，结果自然就出来了

那么就来实现一下代码吧

Golang 实现方式：

基本编码思路如下：

• 定义基本的数据结构
• 对每个工人的单位质量工资进行排序
• 使用最大堆的方式，将对应的 quality 加入到 hp 中，默认先添加前 k 个工人
• 判断 k 个工人之后的有谁的 quality 是比 最大堆顶小的，如果有就替换堆顶，且查看是否需要更新最低成本

func mincostToHireWorkers(quality []int, wage []int, k int) float64 {
    // 定义基本的数据结构
    type pair struct{
        qua int
        wa int
    }
    qw := make([]pair, len(quality))
    for i,q := range quality {
        qw[i].qua = q
        qw[i].wa = wage[i]
    }
    // 对每个工人的单位质量工资进行排序
    sort.Slice(qw, func(i, j int) bool { a, b := qw[i], qw[j]; return a.wa*b.qua < b.wa*a.qua }) // 此处是由 a.wa/a.qua < b.wa/b.qua 转换而来
    // 使用最大堆的方式，将对应的 quality 加入到 hp 中，默认先添加前 k 个工人
    h := hp{make([]int, k)}
    sumQ := 0
    for i, p := range qw[:k] {
        h.IntSlice[i] = p.qua
        sumQ += p.qua
    }
    heap.Init(&h)
    // 判断 k 个工人之后的有谁的 quality 是比 最大堆顶小的，如果有就替换堆顶，且查看是否需要更新最低成本
    res := float64(sumQ*qw[k-1].wa) / float64(qw[k-1].qua) // 选 r 值最小的 k 名工人组成当前的最优解
    for _, p := range qw[k:] {
        if p.qua < h.IntSlice[0] { // sumQ 可以变小，从而可能得到更优的答案
            sumQ -= h.IntSlice[0] - p.qua
            h.IntSlice[0] = p.qua
            heap.Fix(&h, 0) // 更新堆顶
            res = math.Min(res, float64(sumQ*p.wa)/float64(p.qua))
        }
    }
    return res
}
type hp struct{ sort.IntSlice }
func (h hp) Less(i, j int) bool { return h.IntSlice[i] > h.IntSlice[j] } // 最大堆
func (hp) Push(interface{})     {} 
func (hp) Pop() (_ interface{}) { return }

今天就到这里，若有偏差，还请斧正

欢迎点赞，关注，收藏

朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力

好了，本次就到这里

技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。

我是阿兵云原生，欢迎点赞关注收藏，下次见~