有一堆石头,用整数数组 t 表示。其中 t[i] 表示第 i 块石头的重量。
每一回合,从中选出任意两块石头,然后将它们一起粉碎。假设石头的重量分别为 x 和 y,且 x <= y。那么粉碎的可能结果如下:
最后,最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下,就返回 0。
第一行,正整数 n
第二行,数组 t 的 n 个正整数
最后一块石头的重量
输入:
6 2 7 4 1 8 1
输出:
1
解释: 组合 2 和 4,得到 2,所以数组转化为 [2,7,1,8,1], 组合 7 和 8,得到 1,所以数组转化为 [2,1,1,1], 组合 2 和 1,得到 1,所以数组转化为 [1,1,1], 组合 1 和 1,得到 0,所以数组转化为 [1],这就是最优值。
5 31 26 33 21 40
5
1 <= n <= 30
1 <= t[i] <= 100