漯河网站建设网站建设百度免费资源网站

在很久很久以前，有几个部落居住在平原上，依次编号为1到n。第之个部落的人数为 t
有一年发生了灾荒，年轻的政治家小蓝想要说服所有部落一同应对灾荒，他能通过谈判来说服部落进行联台。
每次谈判，小蓝只能邀请两个部落参加，花费的金币数量为两个部落的人数之和，谈判的效果是两个部落联合成一个部落(人数为原来两个部落的人数之和)。
输入描述
输入的第一行包含一个整数 1，表示部落的数量第二行包含 几个正整数，依次表示每个部落的人数。

这道题我用了两种方法 

public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int[] a = new int[n];for (int i = 0; i < n; i++) {a[i] = sc.nextInt();}int sum = 0;System.out.println(getMin(a, sum));}public static int getMin(int[] a, int sum) {if (a.length == 2) {return sum + a[0] + a[1];} else {Arrays.sort(a);int[] aa = new int[a.length - 1];for (int i = 2; i < a.length; i++) {aa[0] = a[0] + a[1];aa[i - 1] = a[i];}sum += aa[0];return getMin(aa, sum);}}

public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();List<Integer> list = new ArrayList<>();for (int i = 0; i < n; i++) {list.add(sc.nextInt());}Collections.sort(list);int sum = 0;while (list.size() > 1) {int num = list.get(0) + list.get(1);sum += num;list.remove(0);list.remove(0);list.add(num);Collections.sort(list);}System.out.println(sum);}

解题主要思想是贪心，只要搞明白之后就能理解了

循环排序 数组或集合计算前两个值之和 放入新数组 再让和累加。最后得到结果