题目描述
给出两个整数序列 $a_1,a_2,\dots ,a_n$ 和 $b_1,b_2,\dots ,b_n$，对 $\{ a_n\}$ 存在如下两种操作：
- 将某个区间的数全部 $+1$
- 将某个区间的数全部 $-1$
试求至少经过多少次操作可以将序列 $\{ a_n\}$ 变为 $\{ b_n\}$
问题分析
事实上，通过等价变换，可以使问题大大简化
首先，我们并不关心 $\{ a_n\}$ 和 $\{ b_n\}$ 具体的数值，影响问题答案的是两者的差异，因此我们对两序列作差，即令 $c_n=a_n-b_n$，此时我们只需要对 $\{ c_n\}$ 进行同样的操作，使得 $\forall i=1,2,\dots ,n$ 都有 $c_i=0$
现在我们引入差分序列的概念
对于序列 $x_1,x_2,\dots ,x_n$，特别规定 $x_0=0$，令 $y_n=x_n-x_{n-1}$ 可以得到新序列 $y_1,y_2,\dots ,y_n$，则 $\{ y_n\}$ 记为 $\{ x_n\}$ 的差分序列，相应地，$\{ x_n\}$ 记为 $\{ y_n\}$ 的前缀和序列
差分与前缀和是一对互逆的序列变换，在静态的区间求和与区间修改问题中，可以将单次操作的复杂度降低为 $O(1)$
引入上述概念后，我们重新审视问题
对序列 $\{ c_n\}$ 作差分，得到差分序列 $\{ d_n\}$，则 $d_i$ 表示原序列中后一项与前一项的差值，我们将原序列中区间 $c_i,c_{i+1},\dots ,c_j$ 全部 $+1$，相当于在差分序列中令 $d_i+1$，并令 $d_{j+1}-1$，该等价性可以通过求前缀和的方式进行验证
至此，问题已经简化为：
已知序列 $d_1,d_2,\dots ,d_n$，每次选取 $i\leq j$，可以令 $d_i+1,d_{j+1}-1$ 或 $d_i-1,d_{j+1}+1$，求将 $\{ d_n\}$ 全部变为 $0$ 的最小操作次数
不难想到贪心策略，每次选取正负性相反的一对 $d_i,d_{j+1}$，其中正数 $-1$，负数 $+1$，最终无法配对的数字与 $d_{n+1}$ 相消（相当于在原序列中，操作该数之后的整个区间）
因此，最终答案即为 $\max \left \{ \sum \limits _{d_i>0} |d_i|,\ \sum \limits _{d_i<0} |d_i| \right \}$，其正确性不难验证，算法的时间复杂度为 $O(n)$
一些细节
- 目标要使所有的 $d_i=0$，因此 $d_1$ 也需要被考虑
- 求和变量应当使用
long long类型，避免溢出
代码
1 |
|