#P1334. 瑞瑞的木板

    ID: 378 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>二叉堆堆排序快速排序排序福建省历届夏令营

瑞瑞的木板

题目背景

瑞瑞想要亲自修复在他的一个小牧场周围的围栏。

题目描述

他测量栅栏并发现他需要 nn 根木板,每根的长度为整数 lil_i。于是,他买了一根足够长的木板,长度为所需的 nn 根木板的长度的总和,他决定将这根木板切成所需的 nn 根木板(瑞瑞在切割木板时不会产生木屑,不需考虑切割时损耗的长度)。

瑞瑞切割木板时使用的是一种特殊的方式,这种方式在将一根长度为 xx 的木板切为两根时,需要消耗 xx 个单位的能量。瑞瑞拥有无尽的能量,但现在提倡节约能量,所以作为榜样,他决定尽可能节约能量。显然,总共需要切割 (n1)(n-1) 次,问题是,每次应该怎么切呢?请编程计算最少需要消耗的能量总和。

输入格式

输入的第一行是整数,表示所需木板的数量 nn

22 到第 (n+1)(n + 1) 行,每行一个整数,第 (i+1)(i + 1) 行的整数 lil_i 代表第 ii 根木板的长度 lil_i

输出格式

一个整数,表示最少需要消耗的能量总和。

3
8
5
8
34

提示

输入输出样例 1 解释

将长度为 2121 的木板,第一次切割为长度为 88 和长度为 1313 的,消耗 2121 个单位的能量,第二次将长度为 1313 的木板切割为长度为 5588 的,消耗 1313 个单位的能量,共消耗 3434 个单位的能量,是消耗能量最小的方案。


数据规模与约定

  • 对于 100%100\% 的数据,保证 1n2×1041\le n \le 2 \times 10^41li5×1041 \leq l_i \leq 5 \times 10^4