过河问题（贪心）

最近学生在外面面试，这道题碰到的比较多，考察对贪心算法的理解和掌握，特此总结一下

---

题目描述：

在漆黑的夜里，N位旅行者来到了一座狭窄而且没有护栏的桥边。如果不借助手电筒的话，大家是无论如何也不敢过桥去的。不幸的是，N个人一共只带了一只手电筒，而桥窄得只够让两个人同时过。如果各自单独过桥的话，N人所需要的时间已知；而如果两人同时过桥，所需要的时间就是走得比较慢的那个人单独行动时所需的时间。问题是，如何设计一个方案，让这N人尽快过桥。

比如有4个人，单独过桥分别需要1，2，5，10分钟，正确答案是17，你算对了吗？

分析一下：
那么这时将单独过河所需要时间最多的两个旅行者送到对岸去，有两种方式:

• 最快的(即所用时间t[0])和次快的过河，然后最快的将船划回来，再次慢的和最慢的过河，然后次快的将船划回来
• 最快的和最慢的过河,然后最快的将船划回来，再最快的和次慢的过河，然后最快的将船划回来。

这样就将过河所需时间最大的两个人送过了河，而对于剩下的人，采用同样的处理方式，接下来做的就是判断怎样用的时间最少

• 方案1所需时间为:t[0]+2*t[1]+t[i-1]
• 方案2所需时间为:2*t[0]+t[i-2]+t[i-1]

如果方式1优于方式2,那么有:t[0]+2t[1]+t[i-1]<2t[0]+t[i-2]+t[i-1] 化简得:2t[1]<t[0]+t[i-2]。即此时只需比较2t[1]与t[0]+t[i-2]的大小关系即可确定最小时间,此时已经将单独过河所需时间最多的两个人送过了河,那么剩下过河的人数为:i-=2,采取同样的处理方式。
如果没过河的人中，除了最快和次快的，就只剩下一个人，那么就由最快的送最慢的过河，最快的回来，最后最快的和次快的一起过河。时间为t[0]+t[i]。最后统一再加上最快和次快的过河时间。

参考代码：

public class Test {
    
    int[] time;
    
    int getTotleTime(int n) {
        if (n <= 2){
            return time[n-1];
        }
        else if (n == 3){
            return time[0] + time[1] + time[2];
        }
        else{
            return getTotleTime(n - 2) + Math.min(time[n-1] + time[n - 2] + 2 * time[0], time[0] + time[1] * 2 + time[n-1]);
        }
    }
}