[ABC307G] Approximate Equalizatio

题意

给定一个数组 \(a_i\) ，有两种操作。

\(a_i+1,a_{i+1}-1\)
\(a_i-1,a_{i+1}+1\)

问最少花费多少次操作能使数组的极差不超过 \(1\)。

题解

容易发现总和不变，由于极差不超过 \(1\) ，设平均数为 \(s\) ，则数组中只有 \(s\) 和 \(s+1\) 两种取值，其中 \(s+1\) 显然只有 \(sum\) % \(n\) 个。
若直接给定结束后的状态，直接从左往右操作，每次直接变成目标，直接将影响交给下一个数，这样其实已经是最小操作次数了。
也就是说设最初 \(i\) 的前缀和为 \(s_i\) ，在结束状态中为 \(s'_i\) ，在 \(i\) 这个位置的操作数为 \(\vert s_i - s'_i \vert\)。
但是现在不知道最终状态，考虑到数据中 \(n\) 只有 \(5000\) ， 所以我们可以使用 \(dp\) 来解决。
容易想到 \(f_{i,j}\) 表示前 \(i\) 个，有 \(j\) 个是 \(s+1\) ，有了这两个我们可以轻易的求出 \(s'_i\) ，之后转移也就很简单了。 code
ps:若总和为负数，所有数字都乘上 \(-1\) 即可，因为操作可以反转。