题解 | 分金条的最小花费

package main

import (
	"container/heap"
	"fmt"
)

type Myheap []int
func (m Myheap) Len() int {return len(m)}
func (m Myheap) Swap(i,j int) {m[i], m[j] = m[j], m[i]}
func (m Myheap) Less(i,j int) bool {return m[i]<m[j]}

func (m *Myheap) Push(x interface{}) {
    *m = append(*m, x.(int))
}
func (m *Myheap) Pop() interface{} {
    x := (*m)[len(*m)-1]
    *m = (*m)[:len(*m)-1]
    return x
}
// 贪心策略求解，将整个拆分过程逆向分为合成过程
// 每次将最小的合成，操作次数降到最低，使得最后的成本最小。
func main() {
    num := 0
    for {
        n, _ := fmt.Scan(&num)
        if n == 0 {
            break
        } else {
            arr := make([]int, num)
            for i:=0; i<len(arr); i++ {
                fmt.Scan(&arr[i])
            }

            var myheap Myheap
            for i:=0; i<len(arr); i++ {
                myheap = append(myheap, arr[i])
            }
            heap.Init(&myheap)
            cost := 0
            for len(myheap) > 1 {
                f1 := (heap.Pop(&myheap)).(int)
                f2 := (heap.Pop(&myheap)).(int)
                costsub := f1+f2
                heap.Push(&myheap, costsub)
                cost += costsub
            }
            fmt.Println(cost)
        }
    }
}