Day02 贪心,前缀和以及差分
2026-08-03 16:35:04
发布于:广东
Day02 贪心,前缀和以及差分
贪心又称为贪婪算法,是求最优解(最大值、最小值)常用的方法。
//所以在使用贪心的时候,需要先排序,用sort最方便。
/*三部曲
1、按要求输入
2、理解题意找到局部最优解进行排序
3、逐一计算符合的
*/
前缀和
//先构造前缀和数组
s[i] = s[i-1] + a[i];
//求区间和L到R之间和
s[R] - s[L-1]
差分
//先构造差分数组
d[i] = a[i] - a[i-1]; //相邻两项的差值
//对区间L到R之间增加C
d[L] += C , d[R+1] -= C; //差分数组只有第L和R项会改变
//最后还原回原数组
a[i] = a[i-1] + d[i]; //由前缀和推导得来,亦可理解为d[i]=a[i]-a[i-1]的变形
这里空空如也












有帮助,赞一个