ApproximateEqualization
[ABC307G] Approximate Equalization
观察操作发现：\(\sum^{n}_{i=1}a_i\) 不会改变。
也就是说，最后的数列中的每个数一定是 \(\lfloor\frac{S}{n}\rfloor\) 或者 \(\lfloor\frac{S}{n}\rfloor+1\)（其中\(S=\sum^{n}_{i=1}a_i\)）
因为序列和是确定的，所以可以得出最终值为这两类数的分别有 \(n-S+n\times \lfloor\frac{S}{n}\rfloor\) 和 \(S-n\times \lfloor\frac{S}{n}\rfloor\) 个。
接下来考虑 dp。
令 \(f_{i,j}\) 表示前 \(i\) 个数中有 \(j\) 个第二类数和 \(i-j\) 个第一类数的最小花费。
考虑转移：最主要的问题是它将相邻的两个数绑在一起操作。
我们现在只考虑对于前 \(i+1\) 个数的操作。因为总和不变，所以我们能得到这样一个式子，其中 \(P\) 为改变后的 \(a_{i+1}\)：
\[P=\sum^{i+1}_{k=1}a_k-j\times(\lfloor\frac{S}{n}\rfloor+1)-(i-j)\times\lfloor\frac{S}{n}\rfloor
\]
应该不难懂。就是前 \(i+1\) 个数的和减掉前 \(i\) 个数的组成部分（可以由当前 dp 状态推导出来）。
接下来就可以转移啦：
\[f_{i+1,j}=\min\{f_{i+1,j},f_{i,j}+|P-\lfloor\frac{S}{n}\rfloor|\}
\]
\[f_{i+1,j+1}=\min\{f_{i+1,j+1},f_{i,j}+|P-(\lfloor\frac{S}{n}\rfloor+1)|\}
\]
复杂度 \(O(n^2)\)。初值 \(f=\{\inf\},f_{0,0}=0\)。
\(S\) 为负时要注意一些细节。
这种方法抛开了原题的操作，用另外一种方式考虑问题。