回分類題庫
g069: D.流水不腐
關鍵字: NPSC 2010 國中組初賽

測資點 : 2 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 109 Times / 86 Users | Submit : 175 Times / 95 Users | Accepted rate : 91%
題目加入時間 : 2012-01-13 16:34

Content: 简体中文

陶侃是晉朝(西元二六五-四二○年)人。他的父親很早就過世了,母親撫養他,特別重視他品德的培養,所以陶侃在各地作官,都有很好的表現。陶侃在廣州作刺史的時候,每天清晨,都把一百塊磚頭從前院搬到後院,又把磚頭從後院搬到前院。旁人看了覺得很奇怪,就問他為甚麼要每天搬磚頭?難道不覺得累嗎?陶侃說:「每天搬磚塊是很累,可是我並不覺得辛苦。搬磚塊,也磨練我的意志,看看自己是不是有恆心,有毅力。」

陶白白是個神奇寶貝大師,聽了個這故事以後決定要效法陶侃,於是他拿出了N 個裝有不同神奇寶貝的寶貝球。神奇的是,神奇寶貝進到寶貝球以後,總重量就變成只有神奇寶貝的重量了(本來應該是神奇寶貝加寶貝球的重量)。陶白白將這N 個裝有不同神奇寶貝的寶貝球隨機地排成一列,由於每一隻神奇寶貝都有一個圖鑑編號,他的鍛鍊目標就是將這些寶貝球按照寶貝球裡神奇寶貝的圖鑑編號由小到大排好順序。

每次陶白白只能將相鄰的兩個寶貝球做交換,但是,因為神奇寶貝的重量很重,所以若他交換了一隻重x 公斤和重y 公斤的神奇寶貝,他晚上就要多吃(x+y) 公克的飯。例如:當他交換了一隻90 公斤的噴火龍和一隻100公斤的妙蛙花。那他晚上就要多吃190 公克的飯。

現在給定原本這N 個寶貝球的順序,問如果要將這些神奇寶貝球按照編號由小到大排序,陶白白晚上最少需要多吃多少公克的飯?

例如:現在有三個寶貝球,按照順序編號分別是 3, 1, 2,重量分別是 3, 2, 1 公斤。則多吃最少飯的方法是先將編號 1 與編號 3 的寶貝球交換( 3 公斤和 2 公斤交換),再將編號 3 與編號 2 的寶貝球交換( 3 公斤和 1 公斤交換)。則所需多吃的飯為 (3 + 2) + (3 + 1) = 9 公克。

Input:

第一行有一個整數T,代表接下來有幾組測試資料。

每一組測試資料第一行有一個整數N,1 ≤ N ≤ 1000。第二行有 N 個整數,第 i 個數字代表原本第 i 個寶貝球裡的神奇寶貝編號,編號不會重複,且編號不超過 2147483647 = 231 − 1。第三行有 N 個整數,第 i 個數字代表原本第 i 個寶貝球裡的神奇寶貝重量(單位:公斤),重量不超過100 公斤。

Output:

對每筆測試資料輸出陶白白晚上最少需要多吃多少克的飯。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
2
3
3 1 2
3 2 1
4
4 3 2 1
10 9 8 7

Sample Output :

9
102

Hint :

Author :

NPSC 2010 國中組初賽 (管理員:sagit)

  Solve it!   Status Forum