题目描述:
给定一个正数数组arr,arr的累加和代表金条的总长度,arr的每个数代表金条要分成的长度。规定长度为K的金条只需分成两块,费用为K个铜板。返回把金条分出arr中的每个数字的最小代价。
public static int split(int[] arr) { if(arr.length < 2) return 0; int res = 0; Queue<Integer> queue = new PriorityQueue<>(); for(int num : arr) { queue.add(num); // 将所有数字加入队列,从小到大合并 } // 这样可以保证合并到只有两个数时,这两个数是最接近的,花费会最小 while (queue.size() >= 2) { int sum = queue.poll() + queue.poll();// 每次取两个最小的合并 res += sum; queue.add(sum); } return res; }