Hướng dẫn cho Tổng Của Hiệu

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: shiba

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*} \]

trong đó \(\sum\limits_{i=1}^{N} a_i\) là tổng của tất cả các \(a_i\) với mọi \(i\) từ \(1\) đến \(N\)

Để 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.


Bình luận