题目大意

就是说现在有序列 $a_1,a_2,a_3,...,a_n$ ，我们每一次操作可以选择一个位置 $i$ ，将 $i$ 这个后缀加或减一些数（如题）。然后我们要求出将序列变成 $k,k,k,k...$的最小操作数。

解题思路

我们先将给出的数组都减去 $k$ 得到一个“需求数组” $c_1,c_2,c_3,..,c_n$，我们的任务就是通过加减填满所有“需求”。但是我们暴力加的话是 $O(n^2)$ 的。

（我原本试图将 $ C_{i - j + p}^{p} $ 拆成 $i,j$ 独立的式子,但失败了。）

先说一个结论：

有两个序列 $A = a_1,a_2,a_3,...$ 和 $B = b_1,b_2,b_3,...$， $A + B$ 的差分序列 $= A$ 的差分序列 $+ B$ 的差分序列。即 $a_i + b_i - a_{i-1} - b_{i-1} = (a_i - a_{i-1}) + (b_i - b_{i-1})$

就是说我们将 ${c_1,c_2,c_3...}$ 和 $C_{p}^{p},C_{p + 1}^{p},C_{p + 2}^{p}...$ 都差分再用后者将前者全补成 $0$ 等价于原问题。有

$$C_{n}^{m} = C_{n - 1}^{m - 1} + C_{n - 1}^{m}$$

在 $C_{p}^{p},C_{p + 1}^{p},C_{p + 2}^{p}...$ 中 $C_{p}^{p} = C_{p - 1}^{p - 1} = 1$,$C_{p + i}^{p} - C_{p + i - 1}^{p} = C_{p + i - 1}^{p - 1}$。也就是说对序列的一次差分就是将上下标都减1。

于是我们只要进行 $p$ 次差分就能将原序列变为 $1,1,1,1...$。$p - 1$ 次差分即为 $1,0,0,0,...$

所以我们将 $c$ 数组也进行 $p - 1$ 次差分,随后答案就是 $ans = \sum_{i = 1}^{n} | c_i |$