切金条

2024-02-15 05:58

文章标签 金条

本文主要是介绍切金条，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一块金条切成两半，是需要花费和长度数值一样的铜板的。比如长度为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铜板。

输入一个数组，返回分割的最小代价

解题方法：

{3, 5, 2, 7, 0, 1, 6, 4 };比如有这样一组数据

被圈住的，，除了16（圈错了）都是分出来的金条

这样分，一定花费的代价是最小的，原因，哈夫曼编码,

没有听说过的话你只需要知道，

从一组数据里面每次拿出最小的两个数，相加再放进数组里，知道剩下一个数据为止

他的所有叶子节点到根节点的代价一定是最小的。

package basic_class_04;
import java.util.*;
public class Main {public static int LessMoney(int[] arr){PriorityQueue<Integer> priority = new PriorityQueue<Integer>();int sum=0;int sur=0;for(int i=0;i<arr.length;i++){priority.add(arr[i]);}while(priority.size()!=1){sur = priority.poll()+priority.poll();sum+=sur;priority.add(sur);}return sum;}public static void main(String[] args) {// TODO Auto-generated method stubint[] arr = {3, 5, 2, 7, 0, 1, 6, 4 };System.out.println(LessMoney(arr));}
}