有n個人想要在晚上過橋,橋上每次最多只能容許2個人行走。由於全部只有一支手電筒,所以每次2個人拿著手電筒過橋後,必須有一人再把手電筒拿回來,這樣後面的人才能繼續過橋。
每個人走路的速度不同,過橋所需的時間也因此不同。而每次過橋的那2個人,其花費的時間以較慢的那個人計算(走的快的當然要等走的慢的,因為只有一支手電筒)。你的任務是寫一個程式,安排這n個人過橋,並使得總共花費的時間最少。
有多筆測試資料。每組測試資料的第一列有1個整數n,代表要過橋的人數(最多不會超過100000人)。接下來的n個整數,代表這n個人過橋所需的時間(秒),這些時間均不會超過1000秒。
每組測試資料輸出的第一列為一個整數,代表這n個人過橋所需的最少時間。
以第一組Sample Output為例說明:最少需17秒才能讓這4個人過橋。方式為:1秒、2秒的人先過橋,1秒的回來,5秒、10秒的過橋,2秒的回來,最後1秒、2秒的過橋,所以總共的時間為:2+1+10+2+2=17。
4 1 2 5 10 4 1 98 99 100 5 1 3 6 8 12
17 299 29
ID | User | Problem | Subject | Hit | Post Date |
25075 | hsugoya@gmai ... (Мигает cf4?) | d872 | 823 | 2021-04-19 21:13 |