最近學生在外面面試，這道題碰到的比較多，考察對貪心算法的理解和掌握，特此總結一下

題目描述：

在漆黑的夜里，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優(yōu)于方式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]的大小關系即可確定最小時間,此時已經將單獨過河所需時間最多的兩個人送過了河,那么剩下過河的人數(shù)為:i-=2,采取同樣的處理方式。
如果沒過河的人中，除了最快和次快的，就只剩下一個人，那么就由最快的送最慢的過河，最快的回來，最后最快的和次快的一起過河。時間為t[0]+t[i]。最后統(tǒng)一再加上最快和次快的過河時間。

參考代碼：

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]);
        }
    }
}