三杉适、貪心算法
1、貪心算法是指学密，在對 問題求解時淘衙，總是做出在當前看來是最好的選擇。也就是說腻暮，不從整體最優(yōu)上加以考慮彤守，他所做出的是在某種意義上的局部 最優(yōu)解。
2哭靖、貪心算法不是對所有問題都能得到整體最優(yōu)解具垫，關(guān)鍵是貪心策略的選擇，選擇的貪心策略必須具備無后效性试幽，即某個狀態(tài)以前的過程不會影響以后的狀態(tài)筝蚕，只與當前狀態(tài)有關(guān)。
一群人想要過河，只有一條船起宽，最多能載兩個人洲胖。因此，必須安排某種航天飛機的安排坯沪，以便使船來回往返卷中，以便所有人都能過馬路阱表。每個人都有不同的劃船速度;一對夫婦的速度是由慢速的速度決定的帆精。你的工作是確定一種策略使這些人的時間減少到最小
輸入：
輸入的第一行包含一個整數(shù)T(1小于=T小于=20)川尖，測試用例的數(shù)量。然后T情況跟進藻糖。每一種情況的第一行包含N淹冰，第二行包含N個整數(shù)，為每個人提供了跨越這條河的時間巨柒。不會有超過1000人樱拴，沒有人會超過100秒。
輸出：
對于每一個測試用例潘拱，打印一條包含所有N人穿越河流所需的秒數(shù)的線疹鳄。
? ? ? 盡可能讓過河時間比較長的兩個一起過河，我們不妨假設(shè)每個人的過河時間是A_1,A_2,......,A_N芦岂。N=1,2,3都是平凡情況容易直接求解瘪弓，只考慮N>=4這個時候，我們關(guān)Sample的構(gòu)造可以看成是Step1-Step5是一個周期禽最，放到對岸腺怯，總共花費時間是：2*A_2+A_1+A_N而問題轉(zhuǎn)化為N-2階的同類型問題。川无，而A_n是無論如何要過河的呛占，不妨就設(shè)為先過A_n-1如果不參與這個四人組過河的話，到后來他的過河時間一定要算進總時間的……那么現(xiàn)在過肯定有利懦趋。故貪心法成立
