首页 > 试题广场 >

分金条的最小花费

[编程题]分金条的最小花费
  • 热度指数：4008 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个正数数组arr，arr的累加和代表金条的总长度，arr的每个数代表金条要分成的长度。规定长度为k的金条分成两块，费用为k个铜板。返回把金条分出arr中的每个数字需要的最小代价。
[要求]
时间复杂度为，空间复杂度为


输入描述:
第一行一个整数N。表示数组长度。

接下来一行N个整数，表示arr数组。


输出描述:
一个整数表示最小代价
示例1

输入

3
10 30 20

输出

90

说明

如果先分成40和20两块，将花费60个铜板，再把长度为40的金条分成10和30两块，将花费40个铜板，总花费为100个铜板；

如果先分成10和50两块，将花费60个铜板，再把长度为50的金条分成20和30两块，将花费50个铜板，总花费为110个铜板；

如果先分成30和30两块，将花费60个铜板，再把其中一根长度为30的金条分成10和20两块，将花费30个铜板，总花费为90个铜板；

因此最低花费为90
示例2

输入

6
3 9 5 2 4 4

输出

67

备注:

算法知识视频讲解
添加回答
Java
牛客513540567号头像 牛客513540567号 
public static void main(String[] args) {  int[] arr = {5,10,6,2,10,21}; //1:创建一个小根堆  PriorityQueue<Integer> heap = new PriorityQueue<>(); //2：入堆  for (int i = 0; i < arr.length; i++) {  heap.add(arr[i]); }  //3:一次弹出两个，进行相加，得到的结果进行标注一下，然后再存放在堆中。直到堆里只剩下一个元素循环才停止。  int count = 0; while (heap.size() > 1) {  int cur = heap.poll() + heap.poll();//注意空指针异常。  count += cur;
        heap.add(cur); }  //4:对特殊标注进行相加  System.out.println(count);; }

发表于 2023-12-01 21:45:06 回复(0)
Java
pein531头像 pein531
每次合并最小的两个数，构建哈夫曼树，这样能够保证整体的花费是最低的 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PriorityQueue<Long> pq = new PriorityQueue<>();
        int n = Integer.parseInt(br.readLine());
        String[] strArr = br.readLine().split(" ");
        for(int i = 0; i < n; i++) pq.offer(Long.parseLong(strArr[i]));
        long cost = 0L;
        // 哈夫曼编码过程
        while(pq.size() > 1){
            long temp = pq.poll() + pq.poll();
            cost += temp;
            pq.offer(temp);
        }
        System.out.println(cost);
    }
}

发表于 2021-11-13 16:05:59 回复(0)
提交观点

问题信息

贪心 堆
上传者：小小
难度：
2条回答 7535浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号