现在有 N 个人想过河，但他们只有一条能容纳两个人的小船，且必须有一个人划船。每个人都有一个过河的时间，两个人在船上时，过河时间取决于较慢的一人。
现在请问要让 N 个人过河最少需要花多少时间？
输入格式
一个整数 T，表示有多少组测试数据。
接下来的 T 组测试数据，每组测试数据第一行是一个正整数 N (1 <= N <= 1000)，表示人数。
接下来一行有 N 个数，第 i 个数表示第 i 个人的过河时间 Ti (0 <= Ti <= 100)。
输出格式
对于每组输入数据，输出一行一个数字，表示最少需要的过河时间。
样例输入
1
4
1 2 5 10样例输出
17
解题思路：当n=1,2,3时所需要的最小时间很容易求得,现在由n>=4,假设n个人单独过河所需要的时间存储在数组t中,将数组t按升序排序,那么 这时将单独过河所需要时间最多的两个旅行者送到对岸去,有两种方式:
1> 最快的(即所用时间t[0])和次快的过河,然后最快的将船划回来,再次慢的和最慢的过河,然后次快的将船划回来.
即所需时间为:t[0]+2*t[1]+t[n-1]
2> 最快的和最慢的过河,然后最快的将船划回来,再最快的和次慢的过河,然后最快的将船划回来.
即所需时间为:2*t[0]+t[n-2]+t[n-1]
这样就将过河所需时间最大的两个人送过了河,而对于剩下的人,采用同样的处理方式,接下来做的就是判断怎样用的时间最少.
#include <stdio.h>
#include <algorithm>
using namespace std;
int t[1000];
int main()
{
int T, n, i;
scanf("%d", &T);
while(T--)
{
scanf("%d", &n);
for(i = 0; i < n; i++)
scanf("%d", &t[i]);
sort(t, t+n);
int sum = 0;
for(i = n-1; i > 2; i -= 2)
{
if(t[0]+2*t[1]+t[i] > 2*t[0]+t[i]+t[i-1])
sum += 2*t[0]+t[i]+t[i-1];
else
sum += t[0]+2*t[1]+t[i];
}
if(i == 0) sum += t[0];
else if(i == 1) sum += t[1];
else if(i == 2) sum += t[0]+t[1]+t[2];
printf("%d\n", sum);
}
return 0;
}