Complexity of an edit distance problem
I give a rough idea to solve the problem in polynomial time.


In the optimal solution, the flow on each edge is unidirectional.
The final value of each element is not far from the mean. Also $\sum_{i&lt;k}A'_i$, the prefix-sum of the optimal $A'$, is bounded in a range at most $O(n^2)$.
Let $T(k,R)$ be the optimal flow on the first $k$ edges such that $\sum_{i&lt;k}A'_i=R$. Then $T(k,R)$ can be computed from $T(k-1,R')$ for all possible $R'$. 


These imply a dynamic programming algorithm with polynomial time complexity.