小强作为强班的班长，决定带着包含他在内的n个同学去春游。路程走到一半，发现前面有一条河流，且只有一条小船。经过实验后发现，这个小船一次最多只能运送两个人，而且过河的时间是等于两个人中体重较大的那个人的体重，如果只有一个人，那么过河时间就是这个人的体重。现在小强想请你帮他分析如何安排才能在最短时间内使所有人都通过这条河流，小强很懒，他并不想知道具体怎么过河，只要你告诉他最短的时间。
输入描述:
第一行输入一个整数T.表示有T组测试数据. 每组数据,第一行输入一个整数n.表示人数. 接下来一行输入n个整数a[i],表示第i个人的体重是a[i]. 1≤T≤101 1≤n≤10^5 1≤a[i]≤10^4
输出描述:
每组测试数据输出一个答案.
输入
2 4 2 10 12 11 4 2 3 7 8
输出
37 19
import java.util.*;/*
第一行输入一个整数T.表示有T组测试数据.
每组数据,第一行输入一个整数n.表示人数.
接下来一行输入n个整数a[i],表示第i个人的体重是a[i].
*/public class AcrossRiver {public static void main(String[] args) {// TODO Auto-generated method stubScanner sc = new Scanner(System.in);int T = sc.nextInt(); // T组for(int i = 0; i < T; i ++) {int n = sc.nextInt(); //总人数nint[] weights = new int[n+1]; // 每个人人的体重，从1开始记录体重，方便后续取值for(int j = 1; j <= n; j ++) {weights[j] = sc.nextInt();}// 体重由轻到重排序，第一个人最轻，最后一个人最重// (这里注意怎么写降序排列https://www.jb51.net/article/204491.htm)Arrays.sort(weights); // Integer[] weight = new Integer[n]; // 降序排列// Arrays.sort(weight, Collections.reverseOrder());int resulttime = 0;/*人数大于4时，过河时先将最重的两个人渡过去，此时有两种思路，一种是最轻的人走2次，每次带一个。另一种是最轻和次轻先过去，最轻回来，最重和次重坐过去，次轻回来。*/while(n >= 4) {// 两种方案的耗时// 1、最轻的带最重的两个人往返// 2、最轻和次轻过，最轻回，最重与次重过，次轻回// 每次重新出发相当于两个人已经到了河对岸，人数-2int planOneTime = weights[1]*2+weights[n]+weights[n-1];int planTwoTime = weights[1]+weights[2]*2+weights[n];resulttime += Math.min(planOneTime,planTwoTime); n -= 2; }// 对剩余人数特判if(n == 3) {resulttime += weights[1] + weights[2] + weights[3];}if(n == 2) {resulttime += weights[2];}if(n == 1) {resulttime += weights[1];}System.out.println(resulttime);}}
}
/*
2
4
2 10 12 11
4
2 3 7 8
*/
