題目連結：
題目大意：
輸入有多筆測試資料，每筆佔兩列。測資第一列給定一正整數 N （N ≦ 100000），代表有 N 張卡片。接著第二列給定 N 個整數 a （a < 100000），代表這 N 張卡片上各自所寫著的數字。
求所有可能的卡片對，其數字差之絕對值的總和為多少？
範例輸入：
4
50 10 30 20
2
100 150
範例輸出：
130
50
解題思維：
直接窮舉每一對求差值然後加總，其時間複雜度 O(N ^ 2)，肯定是會超時的。
我們先將給定的卡片之數字由小到大排序，並重新命名為 A1 、 A2 、 …… 、 AN 。
可以看到所求的總和為
(A2 - A1) + (A3 - A1) + …… + (A3 - A2) + …… + (AN - AN-1)
觀察的數量每一項可以得到一個規律，即數字 Ai （1 ≦ i ≦ N）會為總和貢獻
(i - 1) × Ai - (N - i) × Ai
之值，合併項次可得
(2i - N - 1) × Ai
因此我們排完序後，掃過每個數字求上式的值然後全部加總即是所求。其時間複雜度為 O(N log(N))。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
達人
