poj1700快速渡河问题（贪心策略，详细解析）

二、快速渡河问题
翻译为中文
一队人（N个人）期望跨河，有一条船，一次只能载2个人，过河之后需要有一个人划回来，所有人才能够跨河，每个人划船速度都不同，两个人一组整体速度是由划船速度较慢的决定的。问题：确定一种策略用最少的时间所有人都能过河。

---

输入：
方案数：T（1<=T<=20）
人数:N<1000
速度：<100s
输出：
最少的时间
样例：
输入：
1
4
1 2 5 10
输出
17

---

分析思路：
有两种情况，
第一种：过河时间最少的人来回接送其他人；
第二种：过河时间最少和次少的人来回接送其他人；
4个人过河
首先4个人里面先选2个·，2个已过河的选1个再返回，剩下3个人里面选2个渡河，返回其中一个，最后2个人一起过河
暴力解法：
4人过河
看起来是DFS，一层一层，但是呢，会发现它的规模非常大，并且还有速度在里面，可以便于我们找到最优方案。
速度是1 2 5 10
两人一组由速度最慢的决定

• 一般思路：

1.快的先走，回来快的（带一个慢的，快的去3次，返回2次）；
2.只用最快的来回渡人
假设a,b，c,d依次递增

把上面化解一下
变为2b与a+c

• 代码：

package pojriver;

import java.util.Arrays;
import java.util.Scanner;

public class Pojriver {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int T=sc.nextInt();  //T组数据
		for(int i=0;i<T;i++) {
			int n=sc.nextInt();
			int[] speed=new int[n];
			for(int j=0;j<n;j++) {
				speed[j]=sc.nextInt();
			}
			//排序
			Arrays.sort(speed);
			f(n,speed);  //对速度快慢进行排序
		}
	}
private static void f(int n,int[] speed) {
	int left=n;
	int ans=0;
	while(left>0) {
		if(left==1) { //只有一个人
			ans+=speed[0];
			break;
		}else if(left==2) {  //只有2人
			ans+=speed[1];
			break;
		}
		else if(left==3) { //有3个人
			ans+=speed[2]+speed[0]+speed[1];
			break;
		}
		else {
			//1,2出发，1返回，最后两名出发，2返回
			int s1=speed[1]+speed[0]+speed[left-1]+speed[1];
			//1,3出发，1返回，1,4出发，1返回，1,2过河
			int s2=speed[left-1]+speed[left-2]+2*speed[0]; //a+2b+c
			ans+=min(s1,s2);
			left-=2;  //左侧是渡河起点，left代表左侧的剩余人数
		}
	}
	System.out.println(ans);
}
private static int min(int s1, int s2) {
	return 0;
}
}