#O1031. 合并果子

合并果子

题目描述

有 nn 堆果子,第 ii 堆有 aia_i 个。每次可以合并两堆,消耗的体力等于两堆果子数之和,合并后得到一堆。把所有果子合并成一堆的最小总体力是多少?

题目类型

贪心、优先队列

输入格式

第一行一个整数 nn。

第二行 nn 个整数 aia_i。

输出格式

一行一个整数,表示最小总体力。

样例 #1

样例输入 #1

3
1 2 9

样例输出 #1

15

数据规模与约定

数据范围 说明
1≤n≤1051 \le n \le 10^5 堆数
1≤ai≤1071 \le a_i \le 10^7 每堆果子数
  • 用小根堆每次取最小的两堆,答案可能超过 int。