b584: 過橋問題
Tags : 數論
Accepted rate : 84人/94人 ( 89% ) [非即時]
評分方式:
Tolerant

最近更新 : 2015-10-21 13:26

Content

有一群人要過橋,每個人過橋的速度不同,只有一盞燈,想找出最少要多少時間才能完全過橋,必須滿足下列條件

  1. 一次最多只能過兩個人,必須要有一個人拿燈往返橋的兩邊
  2. 當一人過橋時,過橋的速度就是自己原來的速度
  3. 當兩個人過橋時,速度快的人必須遷就速度慢的人,所以兩個人過橋的時間等於較慢一人的速度

例如有 A,B,C,D,E 五人要過橋,五人速度分別為 11, 7, 4, 2 ,1 單位時間,最好的過橋策略之一就是 DE 過(2) E 回(1),然後 AB 過(11) D 回(2),CE 過(4) E 回(1),最後 DE 過(2),總共花費 2+1+11+2+4+1+2 = 23 單位時間

你的任務就是寫一個程式算出這群人過橋最少要花多少單位時間

Input

每一組測試資料有兩行,第一行是過橋人數 m,1 <= m <= 30,第 2 行有 m 個數字代表他們每一個人需要的過橋單位時間 T(1), T(2),.....,T(m),1 <= T(i) <= 1000. (注意: 輸入的過橋時間不見得會排序)

遇到單行資料 0 就結束

Output

對於每一組測試資料,請輸出過橋時最少要花多少單位時間

Sample Input #1
5
11 7 4 2 1
4
5 5 3 1
0
Sample Output #1
23
15
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (100%): 1.0s , <1K
Hint :

高中計算機概論課本範例
考慮尚未過橋的人 (第二慢的人速度+最快的人速度) > 2*(第二快的人)

Tags:
數論
出處:
SEARCC-ISSC國際學生程式設計競賽 [管理者:
spocktsai (囧rz)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」