a362: 1. 搬雕像
標籤 :
通過比率 : 97% (271 人 / 279 人 ) (非即時)
評分方式:
Tolerant

最近更新 : 2013-05-15 14:45

內容

 

 

王先生是一位收藏家,他收集了非常多有名的雕像。某天,為了美觀,他想
要將收藏台上的雕像按照某種方式重新擺放,由於雕像都有一定的重量,所以他
決定雇用一位年輕人,小明,來幫忙搬雕像。
王先生收藏的雕像目前是以隨機的方式放在收藏台上,收藏台的位置由左至
右成一列排開,編號依序為1, 2,..., n,每個收藏台上放置一個雕像,而收藏台i
(1≤i≤n)上目前放的雕像編號為Si,其高度為hi 公分,重量為wi 公斤。王先生要
求小明依照下列方式去重新擺放雕像:
(a) 搬動過程中,一次只能搬一個雕像,而每個收藏台可暫時放置 0
個、1 個、或多個雕像。
(b) 完成重新擺放之後需符合下列條件:
 每個收藏台上放置一個雕像。
 雕像必須根據高度,由低至高從最左邊的收藏台開始依序放
置。
 若任二雕像的高度相同時,則重量輕的雕像放置在左邊。
 若任二雕像高度和重量都相同時,則依照原先雕像的左右相對
順序來放置,也就是說原先在左邊的雕像必須放置在左邊。
為了節省搬運的距離,小明希望你替他寫出一個程式,根據上述方式將雕像
重新擺放在收藏台上且搬動的總距離為最短。本題假設任二相鄰收藏台的距離為
1 公尺。
以下為一個範例,假設有5 個收藏台,雕像Si (1≤i≤5)的高度和重量以(hi, wi)
表示,並依序為(5,20),(10,25),(78,40),(25,25),(5,15)。一種搬動方式如圖(a)
所示,搬動的總距離為12 公尺,而另一種搬動方式如圖(b)所示,搬動的總距離
為8 公尺,是所有符合搬動方式中的最短距離。

輸入說明
第一行有一個整數n,1≤n≤10000,代表收藏台的個數。接下來的n 行,每
行有兩個整數以空白隔開,其中第i 行(1≤i≤n)為目前放在收藏台i 上雕像Si 的高
度hi(單位為公分)和重量wi(單位為公斤),hi 和wi 都介於1 和65536 之間。
輸出說明
輸出一個整數,代表搬動雕像所需的最短總距離(單位為公尺)。
範例輸入
5
5 20
10 25
78 40
25 25
5 15

8
5 15
3 5
9 13
13 20
24 30
40 50
9 12
5 15
範例輸出
8

18
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (20%): 2.0s , <1K
公開 測資點#1 (20%): 2.0s , <1K
公開 測資點#2 (20%): 2.0s , <1M
公開 測資點#3 (20%): 2.0s , <1M
公開 測資點#4 (20%): 2.0s , <1M
提示 :
標籤:
出處:
100學年度全國資訊學科能力競賽 [編輯:
stanley17112000 (Stanley)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」