学步园

有一艘船只能载两个人，总共有n个人要过河，每个人过河需要时间t[i], 两人共同过河时间为 max(t[i],t[j])，求过河时间最短。

每次载最慢的两个人过河都有两种方法。 可以是t[0] t[1] 一起，也可以是t[0]一个人来回载。

#include <stdio.h>
#include <algorithm>
using namespace std;
#define MAX(x,y) (x<y?y:x)
#define MIN(x,y) (x<y?x:y)
int fun(int n , int g[]){
    if (n==1) return g[0];
    int i,j,sum=0,tmp,cmp1,cmp2;
    tmp=MAX(g[0],g[1])+g[0]+g[1];

    for (j=n-1;j>2;j-=2){
        cmp1=tmp+MAX(g[j],g[j-1]);
        cmp2=2*g[0]+g[j]+g[j-1];
        sum+=MIN(cmp1,cmp2);
    }

    if (j==2) sum+=g[0]+g[1]+g[2];
    if (j==1) sum+=MAX(g[0],g[1]);
    return sum;
}
int g[1050];
int main(){
    int t,i,n;
    scanf("%d",&t);
    while (t--){
        scanf("%d",&n);
        for (i=0;i<n;i++){
            scanf("%d",&g[i]);
        }
        sort(g,g+n);
        printf("%d\n",fun(n,g));
    }
    return 0;
}