題目網址：2231 - Moo Volume

題目概述

農夫約翰擁有 N 頭牛，每一頭牛都會跟另外 N - 1 頭牛交談，所有的牛都處於數線上的一點。

牛與牛之間交談的音量為他們之間的距離絕對值。因此，若 A 牛的座標為 X_A，而 B 牛的座標為 X_B。他們交談的音量則為 X_A - X_B 的絕對值 abs(X_A-X_B)。

現在要求求出所有牛交談的音量總和。

Technique Detail

• 牛的數量 N, 1 ≤ N ≤ 10,000

輸入格式

每一筆測試資料由一個整數 N 開始，表示農夫約翰有 N 頭牛。接下來有 N 行，每行一個整數 X_i ，表示該頭牛所在數線上的座標。

輸出格式

對於每一筆測試資料，輸出只有一行，且只含有一個整數，即為所有牛交談的音量總和。

---

解題思路

最直覺的方法就是，O( N² ) 枚舉每一個配對即可，但 N 的範圍可達 10,000，如此 O( N² ) 的方法必定會造成 TLE，於是需要一個更快的方法。我們將每隻牛的位置畫出來，若以牛的位置做分割點，數線將會被切成一段一段的，共 N - 1 段。

1 - 2 - 3 - … - ( N - 1 ) - N

可以發現：

區段	使用次數
1－2	1 × ( N - 1 ) × 2
2－3	2 × ( N – 2 ) × 2
…	…
( N - 1 )－N	( N - 1 ) × 1 × 2

因為 1－2 這段的左邊有 1 頭牛，右邊有 N – 1 頭牛，每頭牛都會跟另外 N - 1 頭牛交談，因此是雙向的，所以會使用 1 × ( N – 1 ) × 2 次，其他的線段也依此類推…。

因此我們可以在線性的時間 O( N )內求出解。但是，題目並不會依照座標順序給你牛的位置，所以我們必須先做一次排序的動作。所以這題的時間複雜度為 O( N × log N )。

Time Complexity: O( N × log N )

Source Code

Source code on gist.