Làm thế nào để bạn phân vùng một mảng thành 2 phần sao cho hai phần có giá trị trung bình bằng nhau?

Question

Làm thế nào để bạn phân vùng một mảng thành 2 phần sao cho hai phần có giá trị trung bình bằng nhau? Mỗi phân vùng có thể chứa các phần tử không tiếp giáp trong mảng. Thuật toán duy nhất tôi có thể nghĩ đến là theo cấp số nhân chúng ta có thể làm tốt hơn không?

Answer 1

Bạn có thể giảm sự cố này xuống sum-subset problem - cũng cached here. Đây là ý tưởng.

Cho phép A là mảng. Tính theo số S = A[0] + ... + A[N-1], trong đó N có độ dài là A. Đối với k từ 1 đến N-1, hãy để T_k = S * k/N. Nếu T_k là một số nguyên, sau đó tìm một tập con của A có kích thước k có tổng cộng là T_k. Nếu bạn có thể làm điều này, sau đó bạn đã hoàn tất. Nếu bạn không thể làm điều này cho bất kỳ k, thì không có phân vùng như vậy tồn tại.

---

Đây là toán học đằng sau phương pháp này. Giả sử có một phân vùng là A sao cho hai phần có cùng mức trung bình, cho biết X của kích thước x và Y có kích thước y là các phân vùng, trong đó x+y = N. Sau đó, bạn phải có

sum(X)/x = sum(Y)/y = (sum(A)-sum(X))/(N-x) 

do đó, một chút đại số cho

sum(X) = sum(A) * x/N 

Kể từ mảng chứa số nguyên, phía bên tay trái là một số nguyên, vì vậy phía bên tay phải phải là tốt. Điều này thúc đẩy ràng buộc rằng T_k = S * k/N phải là một số nguyên. Phần còn lại duy nhất là nhận ra T_k là tổng của một tập con có kích thước k.