推 smart0eddie: 工作可以重複指定 06/22 04:16
→ smart0eddie: 感覺worker 不用排 06/22 04:16
→ smart0eddie: 工作照profit 排 06/22 04:16
→ smart0eddie: 每個人一直從最高收益往下找到他能做的 06/22 04:16
最後一題
這幾天寫的紀錄完了
之後還是每天紀錄不要偷懶
826. Most Profit Assigning Work
有n件工作、m個工人
三個矩陣
difficulty:difficulty[i]是第i件工作的難度
profit:profit[i]是第i件工作的收益
worker:worker[i]是第i個工人的能力
工人不能做超出他能力的工作，當工人完成工作後可以拿到工作的收益
工人只能做一件工作，一件工作可以被多個工人做，並且收益不變
請問最多可以拿到多少收益
思路：
跟之前的IPO類似
但是因為工作都可以重複做，所以不用用到heap
將profit、difficulty依照difficulty的大小排序
並且也把worker依照能力排序
接著去遍歷worker，記錄滿足worker[i]>=difficulty[j]的最大利益
每次加上這個利益
就可以得到答案了
golang code :
func maxProfitAssignment(difficulty []int, profit []int, worker []int) int {
n, m, res, maxprofit, idx := len(difficulty), len(worker), 0, 0, 0
slices.Sort(worker)
rec := make([][2]int, n)
for key, val := range difficulty {
rec[key][0] = val
rec[key][1] = profit[key]
}
slices.SortFunc(rec, func(i, j [2]int) int { return i[0] - j[0] })
for i := 0; i < m; i++ {
for idx < n && rec[idx][0] <= worker[i] {
maxprofit = max(maxprofit, rec[idx][1])
idx++
}
res += maxprofit
}
return res
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.136.212.164 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1718992205.A.17F.html