package com.jiucaiyuan.net.question;



import java.util.PriorityQueue;



/**

 * 【问题】一个金条切成两半，需要花费和长度一样的铜板。比如：长度为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个铜板

 * 输入一个数组，返回最小代价

 * 经典的哈夫曼编码问题

 * 上来把所有数放到小跟对中，弹出两个数，结合后放入小跟对中，再拿出两个数，结合后放入小跟对，一次类推

 *

 * @Author jiucaiyuan  2022/4/18 23:10

 * @mail services@jiucaiyuan.net

 */

public class LowestMoneySplitGold {



    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 sum = 0;

        int temp = 0;

        while (queue.size() > 1) {

            temp = queue.poll() + queue.poll();

            sum += temp;

            queue.add(temp);

        }

        return sum;

    }



    public static void main(String[] args) {

        int[] arr = {10, 20, 30};

        System.out.println(lessMoney(arr));

    }

}