Day2算法入门、模拟、枚举
2026-08-03 16:06:10
发布于:广东
Day02 贪心,前缀和以及差分
贪心又称为贪婪算法,是求最优解(最大值、最小值)常用的方法。
所以在使用贪心的时候,需要先排序,用sort最方便。
前缀和
先构造前缀和数组
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
最后还原回原数组
a[i] = a[i-1] + d[i]
全部评论 1
hao
2026-08-04 来自 广东
1























有帮助,赞一个