http://poj.org/problem?id=1700
题目大意：
有n个人要过坐船过河，每个人划船有个时间a[i]，每次最多两个人坐一条船过河，且过河时间为两个人中速度慢的，求n个人过河的最短时间。
思路：
贪心。
对于每次过河的，有两种情况：
//最快和最慢过去，然后最快回来，在和次慢过去，最快回来 int action1=a[i-1] + a[0] + a[i-2] +a[0]; //最快和次慢过去，然后最快回来，在次慢和最慢过去，次慢回来 int action2=a[1] +a[0] + a[i-1] +a[1];
每次取最优即可。
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=1024;
int a[MAXN];
int main()
{
int T;
scanf("%d",&T);
while((T--)!=0)
{
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
sort(a,a+n);
int i;
int ans=0;
for(i=n;i>=4;i-=2)
{
//最快和最慢过去，然后最快回来，在和次慢过去，最快回来
int action1=a[i-1] + a[0] + a[i-2] +a[0];
//最快和次慢过去，然后最快回来，在次慢和最慢过去，次慢回来
int action2=a[1] +a[0] + a[i-1] +a[1];
ans=ans+ ( (action1 < action2 )? action1:action2);
}
if(i==3)
ans+= a[0]+a[1]+a[2];
if(i==2)
ans+=a[1];
if(i==1)
ans+=a[0];
printf("%d\n",ans);
}
return 0;
}
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static int[] a=new int[1024];
public static void main(String[] args) {
int T;
Scanner in=new Scanner(System.in);
T=in.nextInt();
while((T--)!=0)
{
int n=in.nextInt();
for(int i=0;i<n;i++)
a[i]=in.nextInt();
Arrays.sort(a,0,n);
int i;
int ans=0;
for(i=n;i>=4;i-=2)
{
//最快和最慢过去，然后最快回来，在和次慢过去，最快回来
int action1=a[i-1] + a[0] + a[i-2] +a[0];
//最快和次慢过去，然后最快回来，在次慢和最慢过去，次慢回来
int action2=a[1] +a[0] + a[i-1] +a[1];
ans=ans+ ( (action1 < action2 )? action1:action2);
}
if(i==3)
ans+= a[0]+a[1]+a[2];
if(i==2)
ans+=a[1];
if(i==1)
ans+=a[0];
System.out.println(ans);
}
}
}