Crossing River

【题目描述】
几个人过河，每次过两人一人回，速度由慢者决定，问过河所需最短时间。

【输入】
输入t组数据，每组数据第1行输入n，第2行输入n个数，表示每个人过河的时间。
【输出】
输出t行数据，每行1个数，表示每组过河最少时间。
【输入样例】

1
4
1 2 5 10

【输出样例】

17

题目分析：
这个题的贪心策略是：可以每次先送过河用时最长的两个人过河，并且每次用过河用时最短的两人将船划回来。 当人数大于三人的时候一共有两种方法：
1.最快的和次快的过河，然后最快的把船划回来，然后次慢和最慢的过河，然后次快的把船划回来，这样所需时间为t[0]+2*t[1]+a[n-1].
2.最快的和最慢的过河，最快的把船划回来，最快的再和次慢的过河，最快的再把船划回来，所需时间为2*t[0]+t[n-2]+t[n-1].
当人数等于三人时最快只有一种方法，所需时间为t[0]+t[1]+t[2](这个就不讲了，自己试试就能知道)
当人数小于三人时，划船用的时间就为用时最长的那个人的时间。
代码如下：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <set>
#include <vector>
#include <string>
#include <cstring>
#include <sstream>
#include <algorithm>
#define LL long long
using namespace std;
const int N=1005;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,a[N],ans=0;
        cin>>n;
        for(int i=0;i<n;i++)
        cin>>a[i];
        sort(a,a+n);
        while(n>3)
        {
            ans+=min(2*a[0]+a[n-1]+a[n-2],a[0]+2*a[1]+a[n-1]);
            n-=2;
        }
        if(n==3) ans+=a[0]+a[1]+a[2];
        else if(n==2) ans+=a[1];
        else ans+=a[0];
        cout<<ans<<endl;
    }
    return 0;
}