Editorial for Tổng Của Hiệu
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Subtask 1
Ta sẽ for lồng tính tổng của từng giá trị \(∣a_i - a_j∣\) thỏa mãn \(1 \le i < j \le N\) và in ra chúng.
Subtask 2
Bây giờ ta sẽ phân tích lại yêu cầu đề bài dưới dạng công thức toán, đề kêu ta tính:
\[
\begin{align*}
\sum_{i=1}^{N-1}\sum_{j=i+1}^N ∣a_i-a_j∣
\end{align*}
\]
Ta sẽ phân tích một chút về phép toán này:
\[
\begin{align*}
\sum_{i=1}^{N-1}\sum_{j=i+1}^N ∣a_i-a_j∣ &= \frac{1}{2} \sum_{i=1}^{N-1}\sum_{j=i+1}^N 2∣a_i-a_j∣ \\
&= \frac{1}{2} \sum_{i=1}^{N-1}\sum_{j=i+1}^N ∣a_i-a_j∣ + ∣a_j-a_i∣ \\
&= \frac{1}{2} \sum_{i=1}^{N}\sum_{j=1}^N ∣a_i-a_j∣ (*) \\
\end{align*}
\]
Để tính \(( * )\) trước tiên ta sẽ sắp xếp dãy theo thứ tự tăng dần xong dùng kỹ thuật prefix sum để giải quyết phép này với độ phức tạp \(O(N)\).
Độ phức tạp tổng của thuật toán này là \(O(NlogN)\) do ta phải sắp xếp dãy nữa.
Comments