Hằng Đẳng Thức
Xem PDFHằng đẳng thức đáng nhớ đã quá quen thuộc rồi. Hãy để sư phụ giới thiệu cho các bạn hằng đẳng thức đáng quên.
có một dãy số \(a\) gồm \(n\) phần tử \(a_1\), \(a_2\), ..., \(a_n\). Hẳng đẳng thức đáng quên của dãy số trên được tính bằng công thức sau:
\(A = \sum |i - j|\), với tất cả các cặp \(i \leq j\) và \(a_i\) = \(a_j\).
Nói cách khác, \(A\) là tổng khoảng cách các vị trí \((i, j)\) mà \(a_i = a_j\).
Các bạn cần tính hằng đẳng thức này như một bài tập về nhà.
Input
-
Dòng đầu tiên chứa một số nguyên dương \(n\) là số phần tử trong mảng \(a\).
-
Dòng tiếp theo chứa \(n\) số nguyên dương \(a_i\) là một phần tử của mảng \(a\).
Output
- Hãy in ra kết quả của hằng đẳng thức đáng quên.
Scoring
-
Trong tất cả các test, \(1 \leq a_i \leq n\).
-
Subtask \(1\) (\(25\%\) số điểm): \(1 \leq n \leq 100\).
-
Subtask \(2\) (\(25\%\) số điểm): \(1 \leq n \leq 1000\).
-
Subtask \(3\) (\(50\%\) số điểm): \(1 \leq n \leq 10^5\).
Example
Test 1
Input
3
2 3 1Output
0Note
Ở ví dụ 1, tất cả các số của \(a\) đều khác nhau, do đó kết quả là 0.
Test 2
Input
4
2 1 2 1Output
4Note
Ở ví dụ 2, \(a_1\) = \(a_3\) = 2 và \(a_2\) = \(a_4\) = 1. Do đó kết quả là (3-1) + (4-2) = 4.
Bình luận
Mình xin chia sẻ lời giải bài này như sau:
Trước tiên, ta phải phân hoạch mảng \(a\) đã cho thành các tập hợp con, trong đó những vị trí nào mà có cùng giá trị thì sẽ thuộc về một tập. (Ta chú ý rằng: các tập hợp con ở đây chỉ chứa vị trí của các phần tử mà có giá trị giống nhau)
Chẳng hạn ở ví dụ \(2\) của đề bài, ta sẽ phân hoạch \((1,2,1,2)\) thành \(2\) tập hợp con, giả sử đó là hai tập \(A=(1,3)\) và \(B=(2,4)\). Vì những vị trí trong tập hợp \(A\) đều có cùng giá trị là \(1\) và những vị trí trong tập hợp \(B\) đều chứa giá trị là \(2\).
Để thực hiện bước phân hoạch này, ta sử dụng \(map<int,vector<int>>\) (Các bạn có thể hiểu rõ hơn ở phần code).
Sau khi đã phân hoạch xong, bước tiếp theo sẽ là tính toán.
Giả sử: Mảng \(a\) của ta được phần thành \(q\) tập hợp con \(S_1,S_2,...,S_q\). Khi đó công thức \(A=\sum\ |i-j| = \sum \limits_{k=1}^{q} F(S_k)\).
Trong đó \(F(S_k)=\sum |S_k[i]-S_k[j]|\) với mọi \(1\le i<j\le n\)
Thì để tính \(S_k\), đầu tiên ta sắp xếp lại mảng \(S_k\) theo thứ tự tăng dần. Và ta có nhận xét rằng: Việc sắp xếp lại mảng không làm ảnh hưởng đến giá trị \(F(S_k)\) nhưng chúng sẽ giúp ta dễ dàng tính được \(F(S_k)\) hơn
Khi đó ta sẽ luôn có: \(S_k[i]<S_k[j]\) với mọi \(1\le i<j\le n\). Tức là: \(F(S_k)=\sum (S_k[j]-S_k[i])\) với mọi \(1\le i<j\le n\)
Đến đây, ta chỉ cần nháp bằng tay ra thì ta dễ dàng tìm được công thức của \(F(S_k)\) như sau:
\(F(S_k) = \sum\limits_{t=2}^{n}((t-1)S_k[t] - presum[t-1])\) trong đó \(presum[t]=S_k[1]+S_k[2]+...+S_k[t]\). Để đảm bảo thuật toán chạy trong thời gian thì ta nên tính trước mảng \(presum\)
Như vậy là bài toán đã được giải quyết xong, các bạn có thể tham khảo code tại đây