这题的难度完全在题目叙述
看了好久还是读不懂
还是去讨论区看人解释才懂
白痴题目
857. Minimum Cost to Hire K Workers
有两个array:quality、wage，分别代表员工的工资工作品质
需要雇用k个员工，请问最少需要付多少工资
需要付的工资为：雇用员工的总quality*员工中最大的(wage[i]/quality[i])
思路:
定义rate[i]为:wage[i]/quality[i]
将员工依照rate来排序
取出前k小的员工
cost为:雇用员工的quality总和*rate[k-1]
接着将这些员工丢到max heap里面
因为rate一样所以max heap依照quality的大小去把员工pop出来
每pop出一个员工就塞一个新的进去
总工资会变成:更新的quality总和*更新的rate
并且跟之前的结果比较看哪个小
就这样把所有员工计算过一轮后
就可以得到最小的工资了
golang code :
type worker struct {
q int
w int
}
type h []worker
func (this h) Len() int {
return len(this)
}
func (this h) Less(i, j int) bool {
return this[i].q > this[j].q
}
func (this h) Swap(i, j int) {
this[i], this[j] = this[j], this[i]
}
func (this *h) Pop() interface{} {
res := (*this)[len(*this)-1]
(*this) = (*this)[:len(*this)-1]
return res
}
func (this *h) Push(x interface{}) {
(*this) = append((*this), x.(worker))
}
func mincostToHireWorkers(quality []int, wage []int, k int) float64 {
n := len(wage)
rec := (make([]worker, n))
for i := 0; i < n; i++ {
rec[i] = worker{q: quality[i], w: wage[i]}
}
sort.Slice(rec, func(i, j int) bool {
return rec[i].w*rec[j].q < rec[j].w*rec[i].q
})
h := h(make([]worker, k))
SumQ := 0
for i := 0; i < k; i++ {
h[i] = rec[i]
SumQ += rec[i].q
}
heap.Init(&h)
minCost := float64(SumQ) * (float64(rec[k-1].w) / float64(rec[k-1].q))
for i := k; i < n; i++ {
tmp := heap.Pop(&h).(worker)
SumQ += rec[i].q - tmp.q
heap.Push(&h, rec[i])
minCost = min(minCost, float64(SumQ)*(float64(rec[i].w)/float64(rec[i].q)))
}
return minCost
}