贪心算法里经典的一个渡河问题
一艘船，每次只能过去两个人，两个人渡河的时间等于其中划船慢的那个人的时间
给你一批人和他们的划船时间，求最小全部渡河的时间
分析：
总人数n<=3时
n=1 t=t[1]
n=2 t=max(t[1],t[2]) 1和2中耗时长的那个
n=3 t=t[1]+t[2]+t[3] 1和3先去,1回来,再和2去
否则:考虑每次送两人过河(其中时间已经排好序了)
1. 1和n去,1回来,1和n-1去,1回来 n-=2 用时2*t[1]+t[n]+t[n-1]
2. 1和2去,1回来,n和n-1去,2回来 n-=2 用时t[1]+2*t[2]+t[n]
每次取两种方法的最小耗时,直到n<=3
AC代码：
#include <stdio.h>
#define N 1001
int t[N];
void Init(int n)
{for(int i=1;i<=n;i++){scanf("%d",&t[i]);}return ;
}
int max(int a,int b)
{return a<b?b:a;
}
int min(int a,int b)
{return a>b?b:a;
}
void quick_Sort(int array[],int left,int right)
{int i=left,j=right,temp;int pivot=array[(i+j)/2];while (i<=j){while(array[i]<pivot) i++;while(array[j]>pivot) j--;if (i<=j){temp=array[i];array[i]=array[j];array[j]=temp;i++;j--;}}if(i<right) quick_Sort(array,i,right);if(left<j) quick_Sort(array,left,j);
}
int solve(int n)
{int sum=0;while (n>=4){sum+=min(t[n]+2*t[2]+t[1],t[n]+t[n-1]+2*t[1]);n-=2;}if(n==3){sum+=t[1]+t[2]+t[3];}if(n==2){sum+=t[2];}return sum;
}
int main()
{int T,n;scanf("%d",&T);while (T--){scanf("%d",&n);Init(n);if(n==1){printf("%d\n",t[1]);}else if(n==2){printf("%d\n",max(t[1],t[2]));}else if(n==3){printf("%d\n",t[1]+t[2]+t[3]);}else{quick_Sort(t,1,n);printf("%d\n",solve(n));}}return 0;
}
//poj 1700