UVa 10037 Bridge

本題連結

題意：
　　每個人的移動速度不一樣，兩個人走時間是以較慢那個人，一次只能兩個人走過去橋的對面，然後需要有一個人把手電筒送回來，求耗費時間最少的方法。

想法：
　　先將數列P排序好，時間由小到大，本題可以分為幾種情況：

1. 只有一個人：直接走過去，時間為P[0]。
2. 兩個人：直接走過去，時間為P[1]。
3. 三個人：P[0],P[1],P[2]，時間為P[1]+P[0]+P[2]
      P[0] P[1]
      P[0]
      P[0] P[2]
4. 三個人以上：如果是偶數個人(例如4個人)，可利用P[0],P[1]不斷將最後面兩個人送到橋的對面，這樣就回到第二點，如果是奇數個人，不斷將最後面兩個送過去就回到第三點。
   將最後面兩個送到橋的對面有兩種方式，設時間最少兩人為P[0],P[1]，最後面兩個人為P[X],P[Y]：
   
   方案A(如Example)： 時間為 P[1]+P[0]+P[Y]+P[1]
      P[0] P[1]
      P[0]
      P[X] P[Y]
      P[1]
   方按B：時間為 P[X]+P[0]+P[Y]+P[0]
      P[0] P[X]
      P[0]
      P[0] P[Y]
      P[0]
   
   因此每次送最後兩個人過去的時候，要比較兩種方式的時間，如果(方案A<方案B)就使用方案A，否則使用方案B。