回分類題庫
h164: D.水晶球傳送問題
關鍵字: NPSC 2016 高中組初賽

測資點 : 4 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 12 Times / 9 Users | Submit : 56 Times / 21 Users | Accepted rate : 43%
題目加入時間 : 2017-11-03 11:49

Content: 简体中文

天龍國是個擁有數千年歷史的古城,他的周遭豎立著 N 座祭壇,每一座祭壇上都存放著一顆相對應的水晶球。古老的文獻中記載著:只要將所有的水晶球完善的保存在相對應的祭壇上,當中蘊藏的魔力就能永遠保護天龍國免於外界的烽火侵襲。

在數千年太平盛世後,原以為能繼續享受安逸生活的天龍國人,萬萬沒想到在一個平常不過的夜晚,天空湧出了巨量異常的外來法力。這法力之強⼤,竟在一夕之間將祭壇上的水晶球都換了位置(仍然是一個祭壇上有一個水晶球)。作為祭壇的守護者,你知道再這樣下去,水晶球的力量撐不久了,天龍國的太平將岌岌可危。於是你決定要以你修煉千年的法力來把水晶球換回相對應的祭壇上。

⽽你能做的是消耗自己的法力來將任意兩個祭壇上的水晶球對調。天龍國周遭的 N 座祭壇各有⼀個傳送的法力門檻 ti ,若要交換第 i 座及第 j 做祭壇上的水晶球,你必須消耗 min(ti, tj)的法力。但是每⼀點法力都是你辛苦修煉得來的,因此,你希望能在消耗最少法力的情形下拯救天龍國的未來。而所剩的時間不多了,你必須先算出最少要消耗的法力! 

舉例而⾔,在第一筆範例測資中,你可以先花費 min(1, 1) = 1 的法力交換第一座及第五座祭壇上的水晶球。交換後,每座上的水晶球編號依序為 1, 4, 3, 2, 5 。接下來再花費 min(1, 1) = 1的法力交換第⼆座及第四座祭壇上的水晶球。交換後,每座上的水晶球編號依序為 1, 2, 3, 4, 5 ,你就完成了你的任務,總共耗費的法力為 1 + 1 = 2 。 

Input:

測試資料第⼀行有一個正整數 T,代表有幾組測試資料。

每組測試資料第⼀行有一個正整數 N,代表有 N 座祭壇。

每組測試資料第二行有 N 個正整數 ti,分別表示第 i 座祭壇傳送的法力門檻。 

每組測試資料第三行有 N 個正整數 si,分別表示第 i 座祭壇上現在的水晶球原本屬於第幾座祭壇。

Output:

針對每組測試資料,請輸出⼀行包含⼀個正整數表示你最少需要消耗的法力。

Sample Input:help

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

Sample Output :

2
11
20

Hint :

Author :

NPSC 2016 高中組初賽 (管理員:sagit)

  Solve it!   Status Forum