因为前缀和/差分学习的时候就不熟,所以特选本题作为训练
作为一道差分题,本题的思路也是特别的绕,首先进行基础知识的复习
【差分】
简单来说就是两个数的差,b[i]=a[i]-a[i-1]
把序列a的区间 [l,r]+d 的话,差分序列b则进行以下变化:
b[l]+d,b[r+1]-d
前置知识大概就这些,下面进行题目分析:
要让序列中的数全部相等,也就是让其之间的差都为0,我们可以让差分后的正数和和负数和取最小,然后加上剩余的部分,这是第一问
第二问是差分后的正数和和负数和的差,具体证明为选择一个个的加/一个个减
警钟长鸣:不开long long 直接爆
标签:Sequence,P4552,long,差分,序列,IncDec From: https://www.cnblogs.com/Jucex/p/18407118