2021-03-04：一块金条切成两半，是需要花费和长度数值一样的铜板的。比如长度为20的金条，不管怎么切，都要花费20个铜板。 一群人想整分整块金条，怎么分最省铜板? 例如,给定数组{10,20,30}，代表一共三个人，整块金条长度为60，金条要分成10，20，30三个部分。如果先把长度60的金条分成10和50，花费60; 再把长度50的金条分成20和30，花费50;一共花费110铜板。但如果先把长度60的金条分成30和30，花费60;再把长度30金条分成10和20， 花费30;一共花费90铜板。输入一个数组，返回分割的最小代价。
福哥答案2021-03-04：
小根堆。
1.数组全部放入小根堆。
2.pop两个数并且相加，和为S。
3.结果里加上S。
4.把S放进小根堆里。
5.重复步骤2。直到数组的长度为1，停止循环。
有代码。
代码用golang编写，代码如下：
package mainimport ( "container/heap" "fmt" "sort")func main() { arr := []int{10, 30, 20} ret := lessMoney(arr) fmt.Println(ret)}func lessMoney(arr []int) int { arrLen := len(arr) if arrLen <= 1 { return 0 } h := IntHeap(arr) heap.Init(&h) ans := 0 twosum := 0 for i := 1; i < arrLen; i++ { twosum = heap.Pop(&h).(int) + heap.Pop(&h).(int) ans += twosum heap.Push(&h, twosum) } return ans}//小根堆type IntHeap sort.IntSlicefunc (c IntHeap) Len() int { return len(c) }func (c IntHeap) Less(i, j int) bool { return c[i] < c[j] }func (c IntHeap) Swap(i, j int) { c[i], c[j] = c[j], c[i] }func (c *IntHeap) Push(x interface{}) { *c = append(*c, x.(int))}func (c *IntHeap) Pop() interface{} { old := *c n := len(old) x := old[n-1] *c = old[0 : n-1] return x}执行结果如下：
左神java代码
评论