剩我不會寫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
}