德州专业网站制作哪家好,怎么建设小型网站,wordpress如何添加封面,仙桃住房和城乡建设部网站1、题目描述 一块金条切成两半#xff0c;是需要花费和长度数值一样的铜板的。比如长度为20的金条#xff0c;不管切成长度多大的两半#xff0c;都要花费20个铜板。 问#xff1a;一群人想整分整块金条#xff0c;怎么分最省铜板#xff1f; 例如#xff0c;给定数组{1…1、题目描述 一块金条切成两半是需要花费和长度数值一样的铜板的。比如长度为20的金条不管切成长度多大的两半都要花费20个铜板。 问一群人想整分整块金条怎么分最省铜板 例如给定数组{102030}代表一共三个人整块金条长度为10203060。 金条要分成102030。如果先把长度60的金条分成10和50花费60再把长度50的金条分成20和30花费50一共花费110铜板。 但是如果先把长度60的金条分成30和30花费60再把长度30金条分成10和20花费30一共花费90铜板。 输入一个数组返回分割的最小代价。
2、思路分析 通过小根堆首先将所有数据加入到小根堆 然后只要小根堆数据个数大于1就弹出两个数并累加 之后再把累加值放到小根堆里去所有的累加和即为最小代价
3 代码实现
public static int lessMoney(int[] arr) {//1、准备一个小根堆PriorityQueueInteger pQ new PriorityQueue();//2、把所有数字扔到小根堆中for (int i 0; i arr.length; i) {pQ.add(arr[i]);}int sum 0;int cur 0;while (pQ.size() 1) {//3、每次弹出两个数字进行结合cur pQ.poll() pQ.poll();sum cur;//4、把结合的数扔到小根堆中pQ.add(cur);}return sum;
}
