1 #include <stdio.h> 2 #include <stdlib.h> 3  4 int main() 5 { 6     int t, i, j, tmp, sum, index; 7     scanf("%d", &t); 8     while(t --) 9     {10         int n, a[1001];11         scanf("%d", &n);12         for(i = 0; i < n; i ++)13         {14             scanf("%d", &a[i]);15         }16         for(i = 0; i < n - 1; i ++)//选择排序17         {18             index = i;19             for(j = i + 1; j < n; j ++)20                 if(a[index] > a[j])21                     index = j;22             tmp = a[index];23             a[index] = a[i];24             a[i] = tmp;25         }26         if(n <= 2)//如果n为1或者为2 的时候，只需要进行一次过桥，时间为最后一个人的27         {28             printf("%d\n", a[n - 1]);29             continue;30         }31         sum = a[1];32         while(n > 3)//当n > 3的时候过桥时间有个规律，最短一共两种，一种是最短时间的那个人带着最长的那个过，然后自己再回来，还有就是先最长的两个过去，第二短的回来，第一第二短在过去，第一短再回来33         {34             if(a[0] + a[n - 1] + a[0] + a[n - 2] > a[n - 1] + a[1] + a[1] + a[0])//这里判断当用最小的运过去与普通方法运过去的大小35                 sum += a[n - 1] + a[1] + a[1] + a[0];36             else37                 sum += a[0] + a[n - 1] + a[0] + a[n - 2];38             n -= 2;//将n减少2,因为一次过去两个39         }40         if(n == 3)//这里判断有两个用途，一个实判断是否是奇数，就是最后还剩三个，还有就是刚开始是奇数的时候41             sum += a[2] + a[0];42         printf("%d\n", sum);43     }44     return 0;45 }