首页 > 试题广场 >

分金条的最小花费

[编程题]分金条的最小花费
  • 热度指数：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

备注:

算法知识视频讲解
开通博客
头像 总之就是非常可爱
发表于 2022-02-15 13:10:21
//本题是哈夫曼算法的应用 //本题大坑：所有的类型要用long long 类型否则会溢出 #include<bits/stdc++.h> using namespace std; //建堆函数 //引用的目的是为了同步改变堆的大小 void heapInsert(long lo 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 快支棱起来的椰子很愤怒
发表于 2022-01-20 17:09:34
n = int(input()) nums = list(map(int, input().split())) import heapq heapq.heapify(nums) res = 0 while len(nums) > 1: a, b = heapq.heappop(nums 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 habitplus
发表于 2021-10-13 10:52:12
Java 自建小顶堆实现 import java.util.PriorityQueue; import java.io.*; public class Main { static final StreamTokenizer st = new StreamTokenizer( 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

贪心 堆
上传者：小小
难度：
13条回答 7641浏览

热门推荐

通过挑战的用户

查看代码

相关试题

分金条的最小花费

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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