## Bài toán yêu cầu bạn tìm số lần truyền đơn vị tối thiểu để cân bằng dãy tròn.
## Một hướng giải là sử dụng mảng tiền tố độ chênh lệch để mỗi thao tác là tối ưu nhất. Có thể giải như sau:
- Bạn dễ dàng thấy -- Tất cả phần tử trong mảng $A$ với $n$ phần tử đều cần phải cân bằng về trung bình tổng $S = \sum_{i=1}^{n} A_i$ của dãy hay $\frac{S}{n}$.
- Các phần tử sẽ có chênh lệch với giá trị cân bằng, bạn có thể lập mảng $d$ ví dụ như sau:
\begin{equation}
d[i] = A[i] - \frac{S}{n}
\end{equation}
- Giả sử mảng cộng dồn $d$ là $pre$, bạn thấy nó cho biết bao nhiêu đơn vị còn dư hoặc thiếu sau khi cân bằng $i$ phần tử đầu tiên, ví dụ:
\begin{equation}
pre[i] = pre[i - 1] + d[i]
\end{equation}
- Bạn có thể nhận xét -- Bài toán biến đổi về cân bằng mảng $pre$ thành một giá trị $X$ bất kì. Khi bạn thay đổi một phần tử trong mảng $pre$, để không phá vỡ *sự thống nhất* của nó với mảng $d$, thì giá trị trong $d$ cũng phải đồng thời bù lại các giá trị do *sự ràng buộc* này.
- Vậy bạn sẽ tìm $X$ như thế nào? Giả sử bạn có một dãy $n$ số không giảm, câu hỏi đặt ra: Khi bạn tìm tổng khoảng cách từ một số trong dãy đến các số còn lại, số nào sẽ cho tổng bé nhất? (Khoảng cách giữa hai số là giá trị tuyệt đối của hiệu hai số ấy)
\begin{equation}
1\quad1\quad2\quad4\quad5\quad8\quad10\quad12\quad13
\end{equation}
- Qua tính toán hoặc suy luận thì giá trị tối ưu nhất nằm tại trung vị (tức $\left\lfloor \frac{n}{2} \right\rfloor$), nên bạn sẽ tìm được đáp án khi các độ chênh lệch gần với giá trị này.
noice
Created at
3 likes