2597. 泉水灌装
1000ms
256MB
简单
题目描述
小 J 来到一处魔法泉水边，他带来了 `n` 个容器。
第 `i` 个容器装满需要 `t_i` 秒。
由于只有一个泉眼，所以小 J 必须一个一个容器地灌装。每个容器从开始排队到灌装完成所经历的时间，等于它前面所有容器的灌装时间之和，再加上它自己的灌装时间。
小 J 希望合理安排容器的灌装顺序，使得所有容器的“从开始排队到灌装完成”的时间总和最小。
请你输出这个最小的时间总和。
输入格式
第一行一个整数 `n`。
第二行 `n` 个整数 `t_1, t_2, ..., t_n`。
输出格式
输出一个整数，表示最小的时间总和。
样例 1
输入 (Input)
输出 (Output)
样例 2
输入 (Input)
输出 (Output)
样例说明
### 样例解释 1
按 `1, 2, 3` 的顺序灌装：
- 第一个容器完成时间：`1`
- 第二个容器完成时间：`1 + 2 = 3`
- 第三个容器完成时间：`1 + 2 + 3 = 6`
总时间为：
```text
1 + 3 + 6 = 10
```
可以证明这是最优顺序。
### 样例解释 2
最优顺序为按时间从小到大：
```text
1, 2, 3, 5
```
完成时间分别为：
```text
1
1 + 2 = 3
1 + 2 + 3 = 6
1 + 2 + 3 + 5 = 11
```
总和为：
```text
1 + 3 + 6 + 11 = 21
```
- $1 <= n <= 10^5$
- $1 <= t_i <= 10^9$
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout
错误 stderr
操作成功