→ Rushia: 他給的例子超爛幹 05/11 17:25
這題的難度完全在題目敘述
看了好久還是讀不懂
還是去討論區看人解釋才懂
白癡題目
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
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.71.214.26 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1715419388.A.9B4.html