数据结构与算法(Java) 44（最小分割代价）数据结构与算法(Java)

题目一块金条切成两半，是需要花费和长度数值一样的铜板的。比如长度为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铜板。输入一个数组，返回分割的最小代价。
思路建立小根堆。每次从堆中取出最小的两个值，计算加和，并将其添加到代价中，再将加和加入到小根堆中，直至小根堆中只剩下一个元素停止。【切割时就从上往下切】（贪心）

package algorithm.section7; import java.util.Comparator; import java.util.PriorityQueue; public class Less_Money { public static int lessMoney(int[] arr){ if (arr.length == 0) return 0; PriorityQueue queue = new PriorityQueue<>(); int sum = 0; for (int value : arr) queue.add(value); while (!queue.isEmpty()){ int min1 = queue.poll(); if (!queue.isEmpty()) { int min2 = queue.poll(); sum += min1; sum += min2; queue.add(min1 + min2); } }return sum; }public static class minHeapComparator implements Comparator{ @Override public int compare(Integer o, Integer t1) { return o - t1; } }public static class maxHeapComparator implements Comparator{@Override public int compare(Integer integer, Integer t1) { return t1 - integer; } }public static void main(String[] args){ int[] arr = {6, 7, 8, 9}; System.out.println(lessMoney(arr)); int[] arr1 = {3, 5, 2, 7, 0, 1, 6, 4}; PriorityQueue queue1 = new PriorityQueue<>(new minHeapComparator()); for (int value : arr1) queue1.add(value); while (!queue1.isEmpty()) System.out.print(queue1.poll() + " "); System.out.println(); PriorityQueue queue2 = new PriorityQueue<>(new maxHeapComparator()); for (int value : arr1) queue2.add(value); while (!queue2.isEmpty()) System.out.print(queue2.poll() + " "); } }

【数据结构与算法(Java) 44（最小分割代价）】