http://acm.nyist.edu.cn/JudgeOnline/problem.php?pid=47
描述
在漆黑的夜里，N位旅行者来到了一座狭窄而且没有护栏的桥边。如果不借助手电筒的话，大家是无论如何也不敢过桥去的。不幸的是，N个人一共只带了一只手电筒，而桥窄得只够让两个人同时过。如果各自单独过桥的话，N人所需要的时间已知；而如果两人同时过桥，所需要的时间就是走得比较慢的那个人单独行动时所需的时间。问题是，如何设计一个方案，让这N人尽快过桥。
输入
第一行是一个整数T(1<=T<=20)表示测试数据的组数
每组测试数据的第一行是一个整数N(1<=N<=1000)表示共有N个人要过河
每组测试数据的第二行是N个整数Si,表示此人过河所需要花时间。(0<Si<=100)
输出
输出所有人都过河需要用的最少时间
样例输入
1 4 1 2 5 10
样例输出
17
在过河的时候肯定要选速度比较快的来送手电筒，现在有a=1， b=2， c=5 ，d=10，如果a和b去，a回来，a和c去，a回来，a和d去，一共花费2+1+5+1+10=19，还有一种是a和b去，b回来，c和d去，a回来，a和b去，花费2+2+10+1+2=17。
不一定是第二种更快，例如a=1，b=5，c=8，d=9时，第一种花费5+1+8+1+9=24，第二种花费5+5+9+1+5=25。
而在有大于4个人的时候，也只需先考虑把最慢的人送出去。所以应该在送人的时候比较两种方案哪种用时更短，不停把速度最慢的送出去，直到最后的人数小于4。
#include<stdio.h>
#include<algorithm>
#define N 1020
using namespace std;
int a[N];
int main()
{
int t,n,i,t1,t2,sum;
scanf("%d",&t);
while(t--)
{
sum=0;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
sort(a,a+n);
while(n>3)
{
t1=a[1]+a[0]+a[n-1]+a[1];
t2=a[n-1]+a[0]+a[n-2]+a[0];
if(t1>t2)
sum+=t2;
else
sum+=t1;
n-=2;
}
if(n==3)
sum+=a[0]+a[1]+a[2];
else if(n==2)
sum+=a[1];
else if(n==1)
sum+=a[0];
printf("%d
",sum);
}
return 0;
}