一块金条切成两半，是需要花费和长度数值一样的铜板的。比如长度为20的金条，不管切成长度多大的两半，都要花费20个铜板。一群人想整分整块金条，怎么分最省铜板。
【一块金条切成两半，是需要花费和长度数值一样的铜板的。比如长度为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铜板。
输入一个数组，返回分割的最小代价。
思路：这个题实际上是哈夫曼编码问题，想把金条断成规定的多少段，选择一个怎样的顺序能让代价最低。一共是10,20,30这三个，10和20合成一个30,30和30合成一个60，共需要代价90 。可以认为每一块是一个叶节点，怎么决定叶节点的合并顺序让整体的合并代价最低。合并代价怎么评估？两个叶节点合并之后产生的和就是它的合并代价。相当于这个题是求所有非叶节点的值加起来谁低。这个题整体就转化为：给了叶节点，选择一个什么合并顺序，能够导致非叶节点整体的求和最小。
具体做法是贪心，怎么证明先忽略，这里主要说怎么用堆来完成这个代价。用小根堆结构，假设有{10,20,30}，先把它组成小根堆，一次从堆里弹出俩，10和20，则小根堆里面还剩下30,10和20组成一个30节点，产生代价30，然后把30节点扔回堆里，然后再从堆里弹出俩，合并完的节点再扔回堆里。如果有多个数的话，所有叶子节点组成一个小根堆，小根堆里一次弹出俩合成一个节点 ，扔回堆里，依次。中途产生的代价依次累加，就是最小代价。
public class Less_Money { public static int lessMoney(int[] arr) {
PriorityQueue 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 {@Override
public int compare(Integer o1, Integer o2) {
return o1 - o2;
} } public static class MaxheapComparator implements Comparator {@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 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 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 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() + " ");
} }}
推荐阅读
- 云花
- 一块玻璃要了九岁男童的命|一块玻璃要了九岁男童的命 家长老师是怎么教育孩子的（）
- 一土司儿野闻
- 五块钱的世界，一块钱的爱
- 2016.10.9调情
- 贪心算法（2）（金条切割问题、点灯问题、IPO问题）
- 沙滩石
- 和女儿共同长
- 船停了
- 中国第一块区块链牌照