首页 > 试题广场 >

分金条的最小花费

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

备注:

这道题你会答吗?花几分钟告诉大家答案吧!