分金条的最小花费

一块金条切成两半,是需要花费和长度数值一样的铜板的。比如 长度为20的 金条,不管切成长度多大的两半,都要花费20个铜 板。一群人想整分整块金 条,怎么分最省铜板? 例如,给定数组{10,20,30},代表一共三个人,整块金条长度为 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铜板。 输入一个数组,返回分割的最小代价。

 

思路：利用哈夫曼编码解决

def getMinSplitCost(L):if L == None or len(L) < 2:return 0queue = []for i in range(len(L)):queue.append(L[i])res = 0while len(queue)!=1:queue = sorted(queue)[::-1]a1 = queue.pop()a2 = queue.pop()res += a1+a2queue.append(res)return res

 

总结

以上是生活随笔为你收集整理的分金条的最小花费的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。