剩我不会写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
}