🎆音乐分享
所谓差分，就是前缀和的逆运算
（不懂前缀和的同学可以去C站看一下😂）
代码
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N], b[N];
int main()
{
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
b[i] = a[i] - a[i - 1]; //构建差分数组
}
int l, r, c;
while (m--)
{
scanf("%d%d%d", &l, &r, &c);
b[l] += c; //将序列中[l, r]之间的每个数都加上c
b[r + 1] -= c; //因为是差分，所以只需要看一下序列的开头和结尾即可
} //开头加一，那么从开头到后面的序列都加一
for (int i = 1; i <= n; i++)
{
a[i] = b[i] + a[i - 1]; //前缀和运算
printf("%d ", a[i]);
}
return 0;
}差分的应用
代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
typedef long long LL;
int n;
int a[N], b[N];
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
for (int i = 1; i <= n; i ++ ) b[i] = a[i] - a[i - 1];//差分数组
LL p = 0, q = 0;
for (int i = 2; i <= n; i ++ )
if (b[i] > 0) p += b[i];//正数加上去
else q -= b[i]; //负数先变成正数，再加上去
cout << max(p, q) << endl;//因为得保证所有项大小一样，所以是max而不是min
cout << abs(p - q) + 1 << endl;
return 0;
}😎使用差分的好处&&为什么要用到abs
对原序列的操作可以变成仅仅对序列 前后两个数 的操作
😎p+=b[i]：因为上面图片中已经了解了b[i]的含义，实际上p+=b[i]就是求出能把b[i]变成0所需要的次数
q-=b[i]同理
😎为什么for循环里面，i是从2开始的，而不是1
我们可以看一下上面的图片的分析过程
b[1]是一个已经确定的数
😎为什么到最后要+1
因为以b[1]为基准（上面图片的分析里面有讲b的含义）
b[i]的值一共有0~|p-q|，一共|p-q|+1种
Code over！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/131379.html
