题目 :
一块金条切成两半，是需要花费和长度数值一样的铜板的。
比如长度为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铜板。
输入一个数组，返回分割的最小代价。
实际上这里等同于如何把数组里三个值花费最小代价拼成60
这里仿照建树规则,新建立的结点值加在一起即是花费的钱数
具体方法,每次从数组中拿两个最小值建树,新得到的值再加入树中,依次类推,直到树得到根.
代码
package com.algorithm.practice.heap;
import java.util.PriorityQueue;
public class LessMoney {
public static int lessMoney(int[] arr){
if (arr==null||arr.length==0){
return 0;
}
PriorityQueue<Integer> queue=new PriorityQueue<>();
for(int i=0;i<arr.length;i++){
queue.add(arr[i]);
}
int cos=0;
while (queue.size()>1){
int min1=queue.poll();
int min2=queue.poll();
cos+=min1+min2;
queue.add(min1+min2);
}
return cos;
}
public static void main(String[] args){
int[] arr = { 6, 7, 8, 9 };//13 17 30
System.out.println(lessMoney(arr));
int[] arrForHeap = { 3, 5, 2, 7, 0, 1, 6, 4 };
}
}
