Tìm tổng sai khác trong một dãy số

[pkpkpk (Ẩn danh)]

Đề bài: Sai khác nhau giữa hai số nguyên là giá trị tuyệt đối của hiệu giữa chúng. Bài toán đặt ra là cho dãy số nguyên a1,a2,…,an. Nhiệm vụ của bạn hãy tính tổng tất cả các sai khác giữa tất cả các cặp số bất kỳ
Input
Dòng đầu là số nguyên dương N (1≤N≤10^6)(1≤N≤10^6)
Dòng thứ hai chứa n số nguyên mỗi số có giá trị tuyệt đối không quá 32768;
Output
Một số nguyên không âm là kết quả của bài toán
Ví dụ
Input
4
4 7 -2 8
Output
33
Giải thích Kết quả |4−7|+|4−(−2)|+|4−8|+|7−(−2)|+|7−8|+|(−2)−8|=3+6+4+9+1+10=33

Bài này em dùng 2 vòng lặp for nhưng bị TLE. Mọi người có thể gợi ý cho em cách làm khác rút gọn thời gian hơn không?

[kisuluoibieng (Tên Gì Cũng Được)]

Bài này là dùng toán nhé
Gợi ý:
Gọi S là tổng của mảng a
Sắp xếp lại mảng a ta vẫn có kết quả không đổi (để tìm công thức tổng quát chứ code không cần sắp xếp)
Tổng sai khác của a1 so với cả dãy:
s1 = (a1 - a1) + (a2 - a1) + (a3 - a1) + … + (an - a1)
Tổng sai khác của a2 so với cả dãy:
s2 = (a2 - a1) + (a2 - a2) + (a3 - a2) + … + (an - a2)
Tổng sai khác của a3 so với cả dãy:
s3 = (a3 - a1) + (a3 - a2) + (a3 - a3) + … + (an - a3)

Tổng sai khác của an so với cả dãy:
sn= (an - a1) + (an - a2) + (an - a3) + … + (an - an)

chỗ in đậm, phép tính bị đảo ngược là vì lấy giá trị tuyệt đối
Đáp án cuối cùng là

S = s1 + s2 … + sn

thử cộng đám công thức trên kia xem có gì hay không

bảo sao học tốt môn toán là một ưu thế

[pkpkpk (Ẩn danh)]

Em thử cộng lại thì được thế này
S = s1 + s2 + s3 + … + sn

= 2(a2 - a1) + 2(a3 - a1) +… + 2(an - a1)
+2(a3 - a2) + 2(a4 - a2) +… + 2(an - a2)
+…
+2(a(n-1) + an)

= 2[ (a2 - a1) + (a3 - a1) + … + (an - a(n-1)) ]

= 2[ a2 + 2a3 + 3a4 + … + (n-1)*a1 -(n-2)*a2 -… - a(n-1)

=> S = 2[ -(n-1)*a1 + a2 - (n-2)a2 + 2a3 - (n-3)*a3 +… + (n-1)*an ]

Em loay hoay tính ra thế này nhưng mà thử áp vào ví dụ thì riêng cái kết quả trong ngoặc vuông đã bằng 33 luôn ạ chứ chưa cần nhân 2 Có phải em cộng sai không ạ?

[rogp10]

Không cần nhân 2 đâu bạn do mỗi cặp chỉ xét một lần.

Với dãy xếp không giảm thì i \geq j \Leftrightarrow a_i \geq a_j
Tức là khi tính ct trị tuyệt đối nếu i > j thì a_i mang dấu cộng, nhỏ hơn thì mang dấu trừ. Xét từng phần tử thì ta sẽ có công thức trên mà không có thừa số 2.