牛客网 IncDec 序列 解答（差分算法 + 分析思路）

原题链接：https://ac.nowcoder.com/acm/contest/999/B
这是一道对思维能力要求较高的题目，一旦理解后解法较为简单，但这种解题方式却不容易想到
解题思路 ：
① 本题的巧妙之处在于运用差分的方式来调整区间数值，从而实现使数列中的所有元素变得一致的目标
② 差分的特性：对于一个特定的数列A，其对应的差分数列B定义为, B[1]=A[1], B[i]=Ai−A[i − 1] (2<=i<=n)， B[1]=A[1], B[i]=Ai−A[i − 1] (2<=i<=n)
此处仅说明其性质，即当对序列A的区间[L,R]增加d时，意味着将A[l], A[l+1]…A[r]均加上d，实际上在差分序列B中体现为B[l]加d、B[r+1]减d，而其余位置保持不变。
③ 题目的目标是通过不断进行+1或-1的操作将序列A转化为所有元素相同的数列。借助差分的特性，该问题可进一步转化为如何将差分序列B中从B[2]到B[n]的所有元素变为0所需的步骤数目。在对原序列A进行操作时，实际上等价于在差分序列B中选取两个元素分别进行加一与减一的操作。
④ 在选取两个元素时存在三种不同的方式：（在B[2]…B[n]范围内选择一个正数和一个负数，并分别进行减一和加一的操作，这种方式能够更快地接近目标）（选择B[1]