推 aioiwer318: 別卷了 06/15 20:52
推 wu10200512: 別卷了 06/15 20:52
→ yam276: 這題沒想像中難啊 就MaxHeap Tree的概念有無 06/15 20:55
→ yam276: 不然每次都sort效率很差 06/15 20:55
推 SecondRun: 哪種人周末還在刷題的 06/15 20:59
剩我不會寫hard了
狗屎爛leetcode
502. IPO
給兩個矩陣profits、capital
w為目前的資本額
當w>=capital[i]時
可以將profits[i]加入資本額中
上述的操作可以做k次
請回傳最大的資本額w
思路:
建立一個n*2的矩陣rec
rec[i][0]=profits[i]
rec[i][1]=capital[i]
將rec依照capital的大小排序
接著用迴圈進行k次操作
將符合w>=rec[i][1]的元素放進maxheap中
並把profit最大的元素拿出來，並且w+=profit
當maxheap裡沒有任何元素時跳出
這樣就可以得到答案了
golang code :
type h []int
func (this h) Len() int { return len(this) }
func (this h) Less(i, j int) bool { return this[i] > this[j] }
func (this h) Swap(i, j int) { this[i], this[j] = this[j], this[i] }
func (this *h) Pop() interface{} {
n := len(*this)
res := (*this)[n-1]
(*this) = (*this)[:n-1]
return res
}
func (this *h) Push(x interface{}) {
(*this) = append(*this, x.(int))
}
func findMaximizedCapital(k int, w int, profits []int, capital []int) int {
var maxheap h
n, idx := len(profits), 0
rec := make([][2]int, n)
for i := 0; i < n; i++ {
rec[i][0] = profits[i]
rec[i][1] = capital[i]
}
slices.SortFunc(rec, func(i, j [2]int) int {
return i[1] - j[1]
})
for i := 0; i < k; i++ {
for idx < n && rec[idx][1] <= w {
heap.Push(&maxheap, rec[idx][0])
idx++
}
if maxheap.Len()<1{
break
}
w += heap.Pop(&maxheap).(int)
}
return w
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.83.34.11 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1718455875.A.ED9.html