我們若不管輸入順序，不管輸入甚麼都先排序，假設輸入為1,2,3,4,5,6。

可以發現答案即為

(2-1)+(3-1)+(4-1)+(5-1)+(6-1)+(3-2)+(4-2)+(5-2)+(6-2)+(4-3)+(5-3)+(6-3)+(5-4)+(6-4)+(6-5)

去掉括號則變成 2-1+3-1+4-1+5-1+6-1+3-2+4-2+5-2+6-2+4-3+5-3+6-3+5-4+6-4+6-5

整合後可以發現，總共有-5個1、-3個2、-1個3、1個4、3個5、5個6。

如果觀察範例測資也會發現此規律，因此整理出：

若將輸入的數字先排序，最小的數總共會有1+N*(-1)個，最大的數總共會有N-1個。

由上可發現每個數字（已排序）的數量其實就是前一個數字的數量+2，將每個數字出現的次數乘以該數字後加總即可。

我們若不管輸入順序，不管輸入甚麼都先排序，假設輸入為1,2,3,4,5,6。

可以發現答案即為

(2-1)+(3-1)+(4-1)+(5-1)+(6-1)+(3-2)+(4-2)+(5-2)+(6-2)+(4-3)+(5-3)+(6-3)+(5-4)+(6-4)+(6-5)

去掉括號則變成 2-1+3-1+4-1+5-1+6-1+3-2+4-2+5-2+6-2+4-3+5-3+6-3+5-4+6-4+6-5

整合後可以發現，總共有-5個1、-3個2、-1個3、1個4、3個5、5個6。

如果觀察範例測資也會發現此規律，因此整理出：

若將輸入的數字先排序，最小的數總共會有1+N*(-1)個，最大的數總共會有N-1個。

由上可發現每個數字（已排序）的數量其實就是前一個數字的數量+2，將每個數字出現的次數乘以該數字後加總即可。

但要注意需要開long long，不然會溢位。

我們若不管輸入順序，不管輸入甚麼都先排序，假設輸入為1,2,3,4,5,6。

可以發現答案即為

(2-1)+(3-1)+(4-1)+(5-1)+(6-1)+(3-2)+(4-2)+(5-2)+(6-2)+(4-3)+(5-3)+(6-3)+(5-4)+(6-4)+(6-5)

去掉括號則變成 2-1+3-1+4-1+5-1+6-1+3-2+4-2+5-2+6-2+4-3+5-3+6-3+5-4+6-4+6-5

整合後可以發現，總共有-5個1、-3個2、-1個3、1個4、3個5、5個6。

如果觀察範例測資也會發現此規律，因此整理出：

若將輸入的數字先排序，最小的數總共會有1+N*(-1)個，最大的數總共會有N-1個。

由上可發現每個數字（已排序）的數量其實就是前一個數字的數量+2，將每個數字出現的次數乘以該數字後加總即可。

我是先把數列排序（以範例一為例）：

10 20 30 50

兩兩之間的差是：

10 10 20

將每種情況列出：

10            

10+10         10

10+10+20   10+20   20

可以整理成

第1個差*1*(項數-1)  + 第二個差*2*(項數-2) + 第3個差*3*(項數-3)

=> 10*1*3 + 10*2*2 +20*3*1

=> 30+40+60

=> 130

所以公式為：

D1*1*(n-1) + D2*2*(n-2) + ........ + Dn*n*1

(D為公差的數列，n為項數）

能想出這樣的規律，真的很厲害。

我們若不管輸入順序，不管輸入甚麼都先排序，假設輸入為1,2,3,4,5,6。

可以發現答案即為

(2-1)+(3-1)+(4-1)+(5-1)+(6-1)+(3-2)+(4-2)+(5-2)+(6-2)+(4-3)+(5-3)+(6-3)+(5-4)+(6-4)+(6-5)

去掉括號則變成 2-1+3-1+4-1+5-1+6-1+3-2+4-2+5-2+6-2+4-3+5-3+6-3+5-4+6-4+6-5

整合後可以發現，總共有-5個1、-3個2、-1個3、1個4、3個5、5個6。

如果觀察範例測資也會發現此規律，因此整理出：

若將輸入的數字先排序，最小的數總共會有1+N*(-1)個，最大的數總共會有N-1個。

由上可發現每個數字（已排序）的數量其實就是前一個數字的數量+2，將每個數字出現的次數乘以該數字後加總即可。

我一開始用這方法卡tle，所以後來把式子化簡了一下，想說乘法少一點看有沒有差(畢竟nlog(n)的排序感覺還是偏肥的)

發現首先頭尾可以合併(第i項跟第n-i-1項)

變成(6-1)*5+(5-2)*3+(4-3)*1

然後可以發現該式相當於

(4-3+5-2+6-1)*1+(5-2+6-1)*2+(6-1)*2

也就是((6-1)+((6-1)+(5-2))+((6-1)+(5-2)+(4-3)))*2 - ((6-1)+(5-2)+(4-3))

令DP[i]表示到第i項之前的首尾相減總和(i<n/2)

最後DP全項加總後-DP[n/2-1]即為所求

PS.自己注意n%2==1跟n%2==0的差別

然後還真的就壓秒過了

AC (1.9s, 848KB)

然後很悲劇的發現最肥的還是i/o

優化之後穩穩的很難過(sad)，所以就來這裡發心得了

我們若不管輸入順序，不管輸入甚麼都先排序，假設輸入為1,2,3,4,5,6。

可以發現答案即為

(2-1)+(3-1)+(4-1)+(5-1)+(6-1)+(3-2)+(4-2)+(5-2)+(6-2)+(4-3)+(5-3)+(6-3)+(5-4)+(6-4)+(6-5)

去掉括號則變成 2-1+3-1+4-1+5-1+6-1+3-2+4-2+5-2+6-2+4-3+5-3+6-3+5-4+6-4+6-5

整合後可以發現，總共有-5個1、-3個2、-1個3、1個4、3個5、5個6。

如果觀察範例測資也會發現此規律，因此整理出：

若將輸入的數字先排序，最小的數總共會有1+N*(-1)個，最大的數總共會有N-1個。

由上可發現每個數字（已排序）的數量其實就是前一個數字的數量+2，將每個數字出現的次數乘以該數字後加總即可。

我一開始用這方法卡tle，所以後來把式子化簡了一下，想說乘法少一點看有沒有差(畢竟nlog(n)的排序感覺還是偏肥的)

發現首先頭尾可以合併(第i項跟第n-i-1項)

變成(6-1)*5+(5-2)*3+(4-3)*1

然後可以發現該式相當於

(4-3+5-2+6-1)*1+(5-2+6-1)*2+(6-1)*2

也就是((6-1)+((6-1)+(5-2))+((6-1)+(5-2)+(4-3)))*2 - ((6-1)+(5-2)+(4-3))

令DP[i]表示到第i項之前的首尾相減總和(i<n/2)

最後DP全項加總後-DP[n/2-1]即為所求

PS.自己注意n%2==1跟n%2==0的差別

然後還真的就壓秒過了

AC (1.9s, 848KB)

然後很悲劇的發現最肥的還是i/o

優化之後穩穩的很難過(sad)，所以就來這裡發心得了

其實這題的IO用scanf和printf就很足夠了XDD