给出n个数,现在要将这n个数合并成一个数,每次只能选择两个数a,b合并,每次合并需要消耗a+b的能量,输出将这n个数合并成一个数后消耗的最小能量。...注意事项
2 <= n <= 50000,合并后的数字不会超过int范围
样例
给出[1,2,3,4],返回 19。...解释:
选择1,2合并,消耗3能量,现在为[3,4,3],选择3,3合并,消耗6,现在为[6,4],剩下两个数合并,消耗10,一共消耗19。
给出[2,8,4,1],返回 25。...解释:
选择1,2合并,消耗3能量,现在为[8,4,3],选择3,4合并,消耗7,现在为[7,8],剩下两个数合并,消耗15,一共消耗25。...贪心算法
一个显而易见的策略是每次我们都找到最小的两个来合并,这样最后加起来的能量应该是最小的。