網頁

2014年1月26日 星期日

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。