http://poj.org/problem?id=1700
题目大意：有n个人要过一条河，每个人过河都需要一个时间，有一艘船，每次过河只能最多装两个人。两个人划船过河所需的时间都取决于过河时间长的那个人，安排一个过河方案，让所有人用最短的时间全部过河。
贪心中经典的过河问题，说实话不看学长的PPT真不会。。。
首先显然要排个序。
n==1和n==2的情况很显然一次过去就完了；
n==3的情况也很显然，a[1]和a[3]过去，a[1]回来，a[1]和a[2]在过去，总共要花a[1]+a[2]+a[3]；
然后考虑n==4的情况，假设四人1-4分别是a,b,c,d，这里就有两种可选方案：
1. 过河顺序为：ac、a、ad、a 时间消耗：t1=2a+c+d
2. 过河顺序为：ab、a(b)、cd、b(a) 时间消耗：t2=a+2b+d
因为t1?t2=a+c?2b，所以选择两种方案的哪一种，和a+c?2b的值有关；
这样不管n等于几，每次可以选第1，2个和第n，n-1个通过以上比较选择更优的方案将第n和n-1个人送过河，直到送到只剩2或3人，参见前面的情况。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
#include <cstdlib>
using namespace std;
int a[1010],T,n;
int main()
{scanf("%d",&T);while(T--){scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);sort(a+1,a+1+n);if(n==1||n==2){printf("%d\n",a[n]);continue;}if(n==3){printf("%d\n",a[n]+a[n-1]+a[1]);continue;}int p=a[1],q=a[2],r=n-1,s=n,ans=0;while(1){if(r==1&&s==2){ans+=a[2];break;}if(r==2){ans+=a[3]+a[2]+a[1];break;}if(p-2*q+a[r]<0){ans+=2*p+a[s]+a[r];s-=2;r-=2;}else{ans+=p+2*q+a[s];s-=2;r-=2;}} printf("%d\n",ans);} return 0;
}