问题链接：。

问题描述：参见上文。

问题分析：这个问题适合于用贪心法来解决，所以需要对输入的数据事先进行排序。

同时还需要考虑特例情况，数据个数小于3的时候，需要特殊处理；数据个数大于3的时候，需要统一处理。

假设人数为n，总的过河时间为：

n=1时，那个人的过河时间；

n=2时，两人中最长的过河时间；

n=3时，总时间是三人过河时间之和。过河时间最短的人，先送一个过河，再回去和另外一个一起过河。

n>=4时，由过河时间最短的人（一人或两人）带过河时间长的人过河。用贪心法首先将过河时间最长的两个人送过河，以此类推，把所有人都送过河，算出来的时间就是最短过河时间。

假设a,b,c,d四人过河，每人过河的时间大小顺序就是a,b,c,d，并且也用a,b,c,d表示他们的过河时间。那么，送过河时间最长的两个人过河，有两种策略，一是用最快的a送，一个一个带过河，四个人过河总时间为2a+b+c+d；二是用最快的两个人a和b送,先a和b过河并且a回来，再让过河时间最长的两个人c和d一起过河并且b回来，四个人过河总时间为a+3b+d。需要从中选择一个时间最短的方案。

上述贪心法重复的步骤中，送过河时间最长两个人过河时，需要从以上的两个方案中选择一个时间最短的方案。

程序说明：（略）。

AC的C语言程序如下：

/* POJ1700 Crossing River */#include 
    
     #include 
     
      int compare(const void*a,const void*b){    return *(int*)a-*(int*)b;}int main(void){    int t, n, s[1005], sum, sum1, sum2, i;    scanf("%d", &t);    while(t-- > 0) {        scanf("%d", &n);        for(i=0; i
      
        3) {            // 每一步将最慢的两个送过河,并且有两种方案可以选择                        // 用最快的一个送(最快和最慢四个过河总时间为2*s[0]+s[1]+s[n-2]+s[n-1])            // 最快的和最慢的先过河,然后最快的一个回来            sum1 = s[0] + s[n-1];            // 最快的和次慢的先过河,然后最快的一个回来            sum1 += s[0] + s[n-2];            // 用最快的两个送(最快和最慢四个过河总时间为s[0]+3*s[1]+s[n-1])            // 最快的两个先过河,然后最快的一个回来            sum2 = s[0] + s[1];            // 最慢的两个人一起过河,次快的一个回来            sum2 += s[1] + s[n-1];            // 上述两个方案中选最小的一个(若2*s[1]>s[0]+s[n-2],则用前一种方案送)            sum += (sum1 < sum2) ? sum1 : sum2;            n -= 2;        }        if(n==1)            sum += s[0];        else if(n==2)            sum += s[1];        else if(n==3)            sum += s[0] + s[1] + s[2];        printf("%d\n", sum);    }    return 0;}