#O1031. 合并果子
合并果子
题目描述
有 堆果子,第 堆有 个。每次可以合并两堆,消耗的体力等于两堆果子数之和,合并后得到一堆。把所有果子合并成一堆的最小总体力是多少?
题目类型
贪心、优先队列
输入格式
第一行一个整数 。
第二行 个整数 。
输出格式
一行一个整数,表示最小总体力。
样例 #1
样例输入 #1
3
1 2 9
样例输出 #1
15
数据规模与约定
| 数据范围 | 说明 |
|---|---|
| 堆数 | |
| 每堆果子数 |
- 用小根堆每次取最小的两堆,答案可能超过
int。
有 n 堆果子,第 i 堆有 ai 个。每次可以合并两堆,消耗的体力等于两堆果子数之和,合并后得到一堆。把所有果子合并成一堆的最小总体力是多少?
贪心、优先队列
第一行一个整数 n。
第二行 n 个整数 ai。
一行一个整数,表示最小总体力。
3
1 2 9
15
| 数据范围 | 说明 |
|---|---|
| 1≤n≤105 | 堆数 |
| 1≤ai≤107 | 每堆果子数 |
int。