分金条的最小花费

[编程题]分金条的最小花费

热度指数：4008 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个正数数组arr，arr的累加和代表金条的总长度，arr的每个数代表金条要分成的长度。规定长度为k的金条分成两块，费用为k个铜板。返回把金条分出arr中的每个数字需要的最小代价。

[要求]

时间复杂度为 $O(n \log n)$ ，空间复杂度为

输入描述:

第一行一个整数N。表示数组长度。

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

输出描述:

一个整数表示最小代价

示例1

输入

3
10 30 20

输出

说明

如果先分成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