一塊金條切成兩半,是需要花費(fèi)和長度數(shù)值一樣的銅板的。比如 長度為20的 金條,不管切成長度多大的兩半,都要花費(fèi)20個(gè)銅 板。一群人想整分整塊金 條,怎么分最省銅板? 例如,給定數(shù)組{10,20,30},代表一共三個(gè)人,整塊金條長度為 10+20+30=60. 金條要分成10,20,30三個(gè)部分。 如果, 先把長 度60的金條分成10和50,花費(fèi)60 再把長度50的金條分成20和30, 花費(fèi)50 一共花費(fèi)110銅板。

但是如果, 先把長度60的金條分成30和30,花費(fèi)60 再把長度30 金條分成10和20,花費(fèi)30 一共花費(fèi)90銅板。 輸入一個(gè)數(shù)組,返回分割的最小代價(jià)。

?

思路：利用哈夫曼編碼解決

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

?

總結(jié)

以上是生活随笔為你收集整理的分金条的最小花费的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。