d932. D. 流水不腐
http://zerojudge.tw/ShowProblem?problemid=d932
內容 ：
陶侃是晉朝 (西元二六五-四二○年) 人。他的父親很早就過世了，母親撫養他，特別重視他品德的培養，所以陶侃在各地作官，都有很好的表現。陶侃在廣州作刺史的時候，每天清晨，都把一百塊磚頭 從前院搬到後院，又把磚頭從後院搬到前院。旁人看了覺得很奇怪，就問他為甚麼要每天搬磚頭？難道不覺得累嗎？陶侃說：「每天搬磚塊是很累，可是我並不覺得 辛苦。搬磚塊，也磨練我的意志，看看自己是不是有恆心，有毅力。」
陶白白是個神奇寶貝大師，聽了個這故事以後決定要效法陶侃，於是他拿出了 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 公克。
輸入說明
：
第一行有一個整數 T ，代表接下來有幾組測試資料。
每一組測試資料第一行有一個整數 N，1 ≤ N ≤ 1000。第二行有 N 個整數，第 i 個數字代表原本第 i 個寶貝球裡的神奇寶貝編號，編號不會重複，且編號不超過 2147483647 = 231 - 1。第三行有 N 個整數，第 i 個數字代表原本第 i 個寶貝球裡的神奇寶貝重量 (單位：公斤)，重量不超過 100 公斤。
輸出說明
：
範例輸入 ：
2 3 3 1 2 3 2 1 4 4 3 2 1 10 9 8 7
範例輸出 ：
9 102
提示
：
出處
：
/**********************************************************************************/
/* Problem: d932 "D. 流水不腐" from 2010 NPSC 國中組初賽 */
/* Language: C */
/* Result: AC (86ms, 276KB) on ZeroJudge */
/* Author: morris1028 at 2011-06-12 19:33:12 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
struct Axis{
int t, v;
}Data[1001], X[1001];
int Ans;
void Merge(int l, int m, int h) {
int In1 = l, In2 = m+1;
int a, b, Top=0, D = 0;
while(In1 <= m && In2 <= h)
if(Data[In1].t < Data[In2].t)
Ans += Data[In1].v*D, X[Top++] = Data[In1++];
else Ans += Data[In2].v*(In2 - (Top+l)), X[Top++] = Data[In2++], D++;
while(In1 <= m) Ans += Data[In1].v*D, X[Top++] = Data[In1++];
while(In2 <= h) Ans += Data[In2].v*(In2 - (Top+l)), X[Top++] = Data[In2++];
for(a = 0, b = l; a < Top; a++, b++)
Data[b] = X[a];
}
void MergeSort(int l, int h) {
if(l < h) {
int m = (l+h)/2;
MergeSort(l , m);
MergeSort(m+1, h);
Merge(l, m, h);
}
}
main() {
int T, n, a;
scanf("%d", &T);
while(T--) {
scanf("%d", &n);
for(a = 0; a < n; a++) scanf("%d", &Data[a].t);
for(a = 0; a < n; a++) scanf("%d", &Data[a].v);
Ans = 0, MergeSort(0, n-1);
printf("%d\n", Ans);
}
return 0;
}
下一篇：d933. E. 傘兵