题目

为腾讯笔试题目，N人过桥问题的改进，N人走钢索，最多两人过钢索，只有一支平衡杆，问最少需要多少时间全部过桥。

输入：
2
3
3 6 9
4
10 1 5 2
含义：有两组人，一组三人，一组四人，组内每人通过时间为下一列数组表示
返回值：
18   （6+3+9）
17   （2+1+10+2+2）

贪心策略
最快的(即所用时间t[0])和次快的过桥,然后最快的回来,再次慢的和最慢的过桥,然后次快的回来。
即所需时间为:t[0]+2*t[1]+t[n-1]
最快的和最慢的过桥，然后最快的回来,再最快的和次慢的过桥,然后最快的回来。
即所需时间为:2*t[0]+t[n-2]+t[n-1]
比较两种情况进行贪心。

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author liujinbo
 * @create 2021-04-04 20:44
 */
public class test2 {
    public static void main(String[] args) {
        Scanner sc =new Scanner(System.in);
        int x =sc.nextInt();
        int[] n1 = new int[x];

        while(sc.hasNext()){
            int n = sc.nextInt();

            int[] num = new int[n+1];

            for (int i = 1; i <=n; i++) {
                num[i] = sc.nextInt();
            }
            Arrays.sort(num);
            int res =0;
            int flag = n;
            while(flag>3){
                if(num[1]+num[flag-1]>2*num[2]){
                    res+=2*num[2]+num[flag]+num[1];
                }else{
                    res+=2*num[1]+num[flag]+num[flag-1];
                }
                flag-=2;
            }
            if(flag==3){
                res +=(num[1]+num[2]+num[3]);
            }else{
                res+=(num[2]);
            }
            System.out.println(res);

        }

    }
}