d872. 過橋問題
Tags :
Accepted rate : 419人/553人 ( 76% ) [非即時]
評分方式:
Tolerant

最近更新 : 2011-02-21 20:33

Content

有n個人想要在晚上過橋,橋上每次最多只能容許2個人行走。由於全部只有一支手電筒,所以每次2個人拿著手電筒過橋後,必須有一人再把手電筒拿回來,這樣後面的人才能繼續過橋。

每個人走路的速度不同,過橋所需的時間也因此不同。而每次過橋的那2個人,其花費的時間以較慢的那個人計算(走的快的當然要等走的慢的,因為只有一支手電筒)。你的任務是寫一個程式,安排這n個人過橋,並使得總共花費的時間最少。

Input

有多筆測試資料。每組測試資料的第一列有1個整數n,代表要過橋的人數(最多不會超過100000人)。接下來的n個整數,代表這n個人過橋所需的時間(秒),這些時間均不會超過1000秒。

 

Output

每組測試資料輸出的第一列為一個整數,代表這n個人過橋所需的最少時間。

以第一組Sample Output為例說明:最少需17秒才能讓這4個人過橋。方式為:1秒、2秒的人先過橋,1秒的回來,5秒、10秒的過橋,2秒的回來,最後1秒、2秒的過橋,所以總共的時間為:2+1+10+2+2=17。 

Sample Input #1
4
1 2 5 10
4
1 98 99 100
5
1 3 6 8 12
Sample Output #1
17
299
29
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 1.0s , <10M
Hint :
這題過了之後就寫UVa ACM Q10037: Bridge吧

Tags:
出處:
UVa10037簡易版 [管理者: david942j (文旋) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
25075 hsugoya@gmai ... (Мигает cf4?) d872
Cross The Bridge
823 2021-04-19 21:13