[title]

Cutting a gold bar in half requires the same amount of copper as the length. For example, gold bars of 20 lengths, no matter how much they cut in half, cost 20 copper plates. A group of people want to divide the whole gold bar, how to divide the most economical copper plate?

For example, given an array {10, 20, 30}, representing a total of three people, the length of the whole bar is 10 + 20 + 30 = 60. Gold bars are divided into 10, 20 and 30 parts.

If, first, the length of 60 gold bars into 10 and 50, cost 60
Divide the 50-length gold bars into 20 and 30 at a cost of 50.
A total of 110 copper plates were spent.

But if you divide a 60-length bar of gold into 30 and 30, it will cost 60.
Divide the length of 30 gold bars into 10 and 20, at a cost of 30.
A total of 90 copper plates were spent.

[input]

Enter an array to return the minimum cost of partitioning.

package basic_class_04;

import java.util.Comparator;
import java.util.PriorityQueue;

public class Code_02_Less_Money {

	public static int lessMoney(int[] arr) {
		PriorityQueue<Integer> pQ = new PriorityQueue<>();
		for (int i = 0; i < arr.length; i++) {
			pQ.add(arr[i]);
		}
		int sum = 0;
		int cur = 0;
		while (pQ.size() > 1) {
			cur = pQ.poll() + pQ.poll();
			sum += cur;
			pQ.add(cur);
		}
		return sum;
	}

	public static class MinheapComparator implements Comparator<Integer> {

		@Override
		public int compare(Integer o1, Integer o2) {
			return o1 - o2;
		}

	}

	public static class MaxheapComparator implements Comparator<Integer> {

		@Override
		public int compare(Integer o1, Integer o2) {
			return o2 - o1;
		}

	}

	public static void main(String[] args) {
		// solution
		int[] arr = { 6, 7, 8, 9 };
		System.out.println(lessMoney(arr));

		int[] arrForHeap = { 3, 5, 2, 7, 0, 1, 6, 4 };

		// min heap
		PriorityQueue<Integer> minQ1 = new PriorityQueue<>();
		for (int i = 0; i < arrForHeap.length; i++) {
			minQ1.add(arrForHeap[i]);
		}
		while (!minQ1.isEmpty()) {
			System.out.print(minQ1.poll() + " ");
		}
		System.out.println();

		// min heap use Comparator
		PriorityQueue<Integer> minQ2 = new PriorityQueue<>(new MinheapComparator());
		for (int i = 0; i < arrForHeap.length; i++) {
			minQ2.add(arrForHeap[i]);
		}
		while (!minQ2.isEmpty()) {
			System.out.print(minQ2.poll() + " ");
		}
		System.out.println();

		// max heap use Comparator
		PriorityQueue<Integer> maxQ = new PriorityQueue<>(new MaxheapComparator());
		for (int i = 0; i < arrForHeap.length; i++) {
			maxQ.add(arrForHeap[i]);
		}
		while (!maxQ.isEmpty()) {
			System.out.print(maxQ.poll() + " ");
		}

	}

}