yes51851823@gmail.com
(wseds)
學校
:
國立花蓮高級工業職業學校
編號 : 108813
來源 : [114.36.253.126]
最後登入時間 ：
2025-08-25 16:32:53
我們若不管輸入順序，不管輸入甚麼都先排序，假設輸入為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，將每個數字出現的次數乘以該數字後加總即可。
yes51851823@gmail.com
(wseds)
學校
:
國立花蓮高級工業職業學校
編號 : 108813
來源 : [114.36.253.126]
最後登入時間 ：
2025-08-25 16:32:53
我們若不管輸入順序，不管輸入甚麼都先排序，假設輸入為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為項數）
asnewchien@gmail.com
(david)
學校
:
南投縣立旭光高級中學
編號 : 68108
來源 : [114.42.176.221]
最後登入時間 ：
2025-10-04 22:52:03
能想出這樣的規律，真的很厲害。
我們若不管輸入順序，不管輸入甚麼都先排序，假設輸入為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)，所以就來這裡發心得了
yes51851823@gmail.com
(wseds)
學校
:
國立花蓮高級工業職業學校
編號 : 108813
來源 : [114.36.253.126]
最後登入時間 ：
2025-08-25 16:32:53
我們若不管輸入順序，不管輸入甚麼都先排序，假設輸入為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