算法-贪心-成本最小切金条

2022-4-18 diaba 算法 

package com.jiucaiyuan.net.question;

import java.util.PriorityQueue;

/**
 * 【问题】一个金条切成两半，需要花费和长度一样的铜板。比如：长度为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个铜板
 * 输入一个数组，返回最小代价
 * 经典的哈夫曼编码问题
 * 上来把所有数放到小跟对中，弹出两个数，结合后放入小跟对中，再拿出两个数，结合后放入小跟对，一次类推
 *
 * @Author jiucaiyuan  2022/4/18 23:10
 * @mail services@jiucaiyuan.net
 */
public class LowestMoneySplitGold {

    public static int lessMoney(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        //默认是小根堆
        PriorityQueue<Integer> queue = new PriorityQueue();
        for (int i = 0; i < arr.length; i++) {
            queue.add(arr[i]);
        }
        int sum = 0;
        int temp = 0;
        while (queue.size() > 1) {
            temp = queue.poll() + queue.poll();
            sum += temp;
            queue.add(temp);
        }
        return sum;
    }

    public static void main(String[] args) {
        int[] arr = {10, 20, 30};
        System.out.println(lessMoney(arr));
    }
}

« 算法-贪心-会议安排问题 | 算法-贪心-拼接字符得到最小字典序»

发表评论：

Powered by emlog 京ICP备15045175号-1 Copyright © 2022