题解 | 小红闯关

倒序遍历数组，当数组下表i % k == 0 && i >= k时，此时一定是有跳关能力的，此时从堆中获取一个最大的值跳过。

package main

import (
    "fmt"
    "container/heap"
)
type Heap []int
func (h Heap) Len() int{
    return len(h)
}
func (h Heap) Less(i,j int) bool{
    return h[i]>h[j]
}
func (h Heap) Swap(i,j int) {
    h[i],h[j] = h[j],h[i]
}
func (h *Heap) Pop() interface{} {
    old := *h 
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}
func (h *Heap) Push(x interface{}) {
    *h = append(*h, x.(int))
}
func main() {
    n,k := 0,0
    fmt.Scan(&n,&k)
    nums := make([]int,n)
    total := 0
    for i := 0;i<n;i++{
        fmt.Scan(&nums[i])
        total += nums[i]
    }
    pq := &Heap{}
    heap.Init(pq)
    sum := 0
    
    for i := n-1;i>-1;i--{
        heap.Push(pq,nums[i])
        if i % k == 0 && i >= k {
            sum += heap.Pop(pq).(int)
        }
        
    }
    fmt.Println(total - sum)

}