个人主页:摆烂小白敲代码 创作领域:算法、C/C++ 持续更新算法领域的文章,让博主在您的算法之路上祝您一臂之力 欢迎各位大佬莅临我的博客,您的关注、点赞、收藏、评论是我持续创作最大的动力
差分算法是一种在计算机科学中常用的算法,特别是在处理序列数据时,它可以帮助我们快速计算出序列中相邻元素的差值。时间复杂度可以达到O(1),在C++中实现差分算法不仅可以提高程序的效率,还可以简化代码的复杂度。本文将详细介绍差分算法的原理、C++实现方法以及算法例题。
上一篇博客一篇带你速通前缀和算法(C/C++)-CSDN博客我们介绍了前缀和算法,这一篇文章就与前缀和算法相反为差分算法。
差分算法的核心思想是利用已有的数据序列,通过计算相邻元素之间的差值来生成一个新的序列。对于一个给定的序列 a=[a1,a2,...,an],其差分序列 d 可以表示为:d[i]=a[i]−a[i-1]。差分数组长度一般为原定序列长度+1,即:len=n+1。其中,d[0] 通常被定义为0,或者根据具体应用场景进行特殊处理。我们设原数组序列为a=[3,1,5,4,2],下标从1开始,那么差分数组可以由d[i]=a[i]−a[i-1]求得,如下图所示。
一维差分在修改区间时效率非常高,时间复杂度可以达到 O(1),我们通过对差分数组的修改以达到修改原数组的目的,那么如何修改差分数组,比如在数组a的[l,r]区间上的数统一+c,转化为差分数组为d[l]+c,d[r+1]-c,这样我们再利用前缀和还原便可以得到原数组修改后的值。在还原时,只需要将前i位差分数组相加便可以得到原数组,比如还原第三位,a[3]=d[1]+d[2]+d[3],便可以还原其值,其还原的第n+1位一定是0。
我们设原数组序列为 a=[3,1,5,4,2],设d为差分数组,在[2,4]区间上的值统一+2,下面我们将模拟实现。
我们需要在[2,4]区间上的值统一+2,那么转换为差分数组d[l]+c,d[r+1]-c==d[2]+2,d[4+1]-2。我们代入到过程实现一下。
原数组序列为 a=[3,1,5,4,2],在[2,4]区间上的值统一+2,我们将得到a=[3,3,7,6,2],与差分还原的来是一样的。
前面我们讲述的是一维差分,其数组为一维的,其模型可以抽象为线性的。那么有些时候需要我们使用二维差分,当题目出现矩阵时,说明就涉及到了二维差分,其模型可以抽象为矩阵,二维差分稍微比一维差分难一点,主要是在处理区间更新时。我们设d[i][j]为(1,1)点到(i,j)点的差分子矩阵(1<=x<=i,1<=y<=j),此时我们设a[i][j]=Σd[i][j](1<=x<=i,1<=y<=j),即a[i][j]=差分矩阵的和。
当我们需要构造差分数组实现修改区间的值时,此时的递推关系式不再是跟一维差分相同,由于是二维的,所以转化为在一个矩阵上+c,在一个矩阵上-c,那么如何确定这两个矩阵。假设我们在(x1,y1)->(x2,y2)这个矩阵统一加C,那么转化为差分矩阵的操作为
d[x1][y1]+C
d[x1][y2+1]-C
d[x2+1][y1]-C
d[x2+1][y2+1]+C
//上面操作等价于
for(int i=x1;i<=x2;i++)
for(int j=y1;j<=y2;j++)
a[i][j]+=C;
在构造差分矩阵时,可以先初始化一个差分矩阵都为0,把自己的点,(x,y)->(x,y)插入到差分矩阵中,代码如下:
void insert(int x1, int y1, int x2, int y2, int c)//构造差分矩阵
{
b[x1][y1] += c;
b[x2 + 1][y1] -= c;
b[x1][y2 +1] -= c;
b[x2 +1][y2+1] +=c;
}
d[x1][y1]+C相当于原矩阵A矩阵(黄色)每个值都+C
d[x2+1][y2+1]+C相当于整个矩阵A+B+C+D矩阵每个值都+C
此时A矩阵+2C,B矩阵+C,C矩阵+C,D矩阵+C,我们再设法把不需要的减掉。
d[x1][y2+1]-C相当于A+B矩阵(黄色+绿色)都-C
此时A矩阵+C,B矩阵+0,C矩阵+C,D矩阵+C,我们再设法把不需要的减掉。
d[x2+1][y1]-C相当于A+C矩阵(黄色+蓝色)都-C
此时A矩阵+0,B矩阵+0,C矩阵+0,D矩阵+C,达到了我们所需要的(x1,y1)到(x2,y2)加C的目的。
最后就是还原其值,利用前缀和的思想,如上图所示,要求(1,1)->(x2,y2)的值,那么可以转化为矩阵(1,1)->(x2,y2-1)与(1,1)->(x2-1,y2)的和减去(1,1)->(x2-1,y2-1)矩阵的值,最后再加上自身值d[x2][y2]。其递归式为d[i][j] += d[i - 1][j] + d[i][j - 1] - d[i - 1][j - 1]。
for (int i = 1; i <= n; i++)//二维前缀和还原
{
for (int j = 1; j <= m; j++)
{
d[i][j] += d[i - 1][j] + d[i][j - 1] - d[i - 1][j - 1];
}
}
#include<iostream>
using namespace std;
const int N =1010;
int a[N][N],d[N][N];
int n,q;
void insert(int x1, int y1, int x2, int y2, int c)
{
d[x1][y1] += c;
d[x2 + 1][y1] -= c;
d[x1][y2 +1] -= c;
d[x2 +1][y2+1] +=c;
}
int main()
{
scanf("%d%d", &n,&q);
for(int i = 1;i <= n; i++){
for(int j = 1;j <= n; j++){
cin >> a[i][j];
insert(i, j, i, j, a[i][j]);
}
}
while( q-- )
{
int x1, x2, y1, y2,c;
cin >> x1 >> y1>> x2 >> y2 >> c ;
insert(x1 ,y1, x2, y2, c);//修改区间
}
//求前缀和
for(int i = 1; i<=n; i++){
for(int j = 1; j<=n; j++){
d[i][j] += d[i][j-1] + d[i-1][j] - d[i-1][j-1];
printf("%d ", d[i][j]);
}
cout<<endl;
}
return 0;
}
Farmer John 的 N 头奶牛对他们牛棚的室温非常挑剔。
有些奶牛喜欢温度低一些,而有些奶牛则喜欢温度高一些。
Farmer John 的牛棚包含一排 N 个牛栏,编号为 1…N,每个牛栏里有一头牛。
第 i 头奶牛希望她的牛栏中的温度是 pi,而现在她的牛栏中的温度是 ti。
为了确保每头奶牛都感到舒适,Farmer John 安装了一个新的空调系统。
该系统进行控制的方式非常有趣,他可以向系统发送命令,告诉它将一组连续的牛栏内的温度升高或降低 1 个单位——例如「将牛栏 5…8 的温度升高 1 个单位」。
一组连续的牛栏最短可以仅包含一个牛栏。
请帮助 Farmer John 求出他需要向新的空调系统发送的命令的最小数量,使得每头奶牛的牛栏都处于其中的奶牛的理想温度。
输入的第一行包含 N。
下一行包含 N 个非负整数 p1…pN,用空格分隔。
最后一行包含 N 个非负整数 t1…tN。
输出一个整数,为 Farmer John 需要使用的最小指令数量。
数据范围
1≤N≤10^5 0≤pi,ti≤10000
输入样例:
5
1 5 3 3 4
1 2 2 2 1
输出样例:
5
样例解释
一组最优的 Farmer John 可以使用的指令如下:
初始温度 :1 2 2 2 1
升高牛棚 2..5:1 3 3 3 2
升高牛棚 2..5:1 4 4 4 3
升高牛棚 2..5:1 5 5 5 4
降低牛棚 3..4:1 5 4 4 4
降低牛棚 3..4:1 5 3 3 4
一个数组转化到另一个数组,我们可以考虑利用差分,快速解决,在一个区间上所有的数加上一个数k或者减去一个数k,我们可以等价转化为差分数组在区间两端一个+k一个-k。题目中起始数组到目标数组,我们可以把这两个数组做差值,然后差值数组变为差分数组,等价为转化到全零数组。差分数组每个值加和必为0(此题必有解),因为我们每次只相当于在差分数组两个值上加减,一个加一个减,要到达0数组,那肯定小于0的每次+1,直到为0,大于0的每次-1,直到为0。
p数组: 1 5 3 3 4
t数组: 1 2 2 2 1
差值数组:0 3 1 1 3
差分数组:0 3 -2 0 2 -3
第一次: 0 2 -1 0 2 -3
第二次: 0 1 0 0 2 -3
第三次: 0 0 0 0 2 -2
第四次: 0 0 0 0 1 -1
第五次: 0 0 0 0 0 0
所以只需要统计大于0或者小于0的值即可
#include<iostream>
using namespace std;
const int N=1e5+5;
int n,ans;
int p[N],t[N];//p数组既作为p数组又作为差分数组
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>p[i];
}
for(int i=1;i<=n;i++){
cin>>t[i];
p[i]-=t[i];
}
//差分p[i]=p[i]-p[i-1],差分数组边界p[1]=p[1],p[n+1]=-p[n]
for(int i=n+1;i>=1;i--){//因为i要先于i-1更新,所以逆序遍历
p[i]-=p[i-1];
}
for(int i=1;i<=n+1;i++){//只要遍历大于0或者小于零的p[i]累加即可
if(p[i]>0){
ans+=p[i];
}
}
cout<<ans<<endl;
return 0;
}
某公司养有观赏花,这些花十分娇贵,每天都需要且仅需要浇水一次。
如果某一天没给花浇水或者给花浇水超过一次,花就会在那一天死亡。
公司即将迎来 n 天假期,编号 1∼n。
为了让花能够活过整个假期,公司领导安排了 m 个人(编号 1∼m)来公司浇花,其中第 i 个人在第 [ai,bi] 天每天来公司浇一次花。
领导是按照时间顺序安排的浇花任务,保证了对于 1≤i≤m−1,均满足:bi≤ai+1。
给定领导的具体安排,请你判断,花能否活过整个假期,如果不能,请你输出它是在第几天死的,以及那一天的具体浇水次数。
第一行包含两个整数 n,m。
接下来 m 行,每行包含两个整数 ai,bi。
输出一行结果。
如果花能活过整个假期,则输出 OK
。
如果花不能活过整个假期,则输出两个整数 x,y,表示花是在第 x 天死的,这一天花被浇了 y 次水。
数据范围
前 4 个测试点满足 1≤n,m≤10。 所有测试点满足 1≤n,m≤10^5,1≤ai≤bi≤n。
输入样例1:
10 5
1 2
3 3
4 6
7 7
8 10
输出样例1:
OK
输入样例2:
10 5
1 2
2 3
4 5
7 8
9 10
输出样例2:
2 2
输入样例3:
10 5
1 2
3 3
5 7
7 7
7 10
输出样例3:
4 0
这道题其实一眼看上去是区间合并问题,这里我们讲解的差分算法,那么我们就用差分解决此题。员工在一个区间内浇水那么就可以视为区间修改,可以构造差分数组快速解决,这道题还一个条件就是花不能多浇水,这个实现也可以在差分数组之中,我们可以利用前缀和还原差分数组得到此朵花被浇了几次水,进而判断此花是否存活。
#include<iostream>
using namespace std;
const int N = 1e5 + 5;
int n,m;
int b[N];
int main(){
cin >> n >> m;
while(m--){
int l,r;
cin >> l >> r;
b[l]++;//构造差分数组
b[r + 1]--;
}
for(int i = 1;i <= n;i++){
b[i] = b[i] + b[i - 1];//前缀和还原
if(b[i] > 1 || b[i] < 1) {//超过一次浇水或者一次也没有浇水
cout << i << ' ' << b[i] << endl;
return 0;
}
}
cout << "OK" << endl;
return 0;
}
在大学期间,经常需要租借教室。
大到院系举办活动,小到学习小组自习讨论,都需要向学校申请借教室。
教室的大小功能不同,借教室人的身份不同,借教室的手续也不一样。
面对海量租借教室的信息,我们自然希望编程解决这个问题。
我们需要处理接下来 n 天的借教室信息,其中第 i 天学校有 ri 个教室可供租借。
共有 m 份订单,每份订单用三个正整数描述,分别为 dj,sj,tj,表示某租借者需要从第 sj 天到第 tj 天租借教室(包括第 sj 天和第 tj 天),每天需要租借 dj 个教室。
我们假定,租借者对教室的大小、地点没有要求。
即对于每份订单,我们只需要每天提供 dj 个教室,而它们具体是哪些教室,每天是否是相同的教室则不用考虑。
借教室的原则是先到先得,也就是说我们要按照订单的先后顺序依次为每份订单分配教室。
如果在分配的过程中遇到一份订单无法完全满足,则需要停止教室的分配,通知当前申请人修改订单。
这里的无法满足指从第 sj 天到第 tj 天中有至少一天剩余的教室数量不足 dj 个。
现在我们需要知道,是否会有订单无法完全满足。
如果有,需要通知哪一个申请人修改订单。
第一行包含两个正整数 n,m,表示天数和订单的数量。
第二行包含 n 个正整数,其中第 i 个数为 ri,表示第 i 天可用于租借的教室数量。
接下来有 m 行,每行包含三个正整数 dj,sj,tj,表示租借的数量,租借开始、结束分别在第几天。
每行相邻的两个数之间均用一个空格隔开。
天数与订单均用从 1 开始的整数编号。
如果所有订单均可满足,则输出只有一行,包含一个整数 0。
否则(订单无法完全满足)输出两行,第一行输出一个负整数 −1,第二行输出需要修改订单的申请人编号。
数据范围
1≤n,m≤10^6 0≤ri,dj≤10^9 1≤sj≤tj≤n
输入样例:
4 3
2 5 4 3
2 1 3
3 2 4
4 2 4
输出样例:
-1
2
此题可用差分+二分或者线段树来解,由于博主能力限制这里会由易懂的差分+二分来讲解。这道题第一感觉应该就是差分了吧,修改区间的值,用差分效率更高一点。我们可以把申请人的需要转化成差分数组,利用前缀和还原,判断i个教室是否满足。如果我们只依靠差分是解决不了此题的,只利用差分时间复杂度为O(nm),大约10^12,肯定会超时,那么我们可以考虑把内层循环利用二分优化掉,具体咋优化呢,我们有了一个申请人编号的差分数组,从第一位申请单到最后一个申请单,越在前面的越容易借到教室,说明教室剩余够多,越到后面剩余可借教室会减少,因为会被前面的申请借去,那就说明第一个不满足的编号越往后概率越高,这样是不是感觉像是一个有序的序列,从头到尾,能满足的概率是由大到小的。那么我们利用二分去查到最后一个能满足的订单,+1即为不能满足的订单,上代码。
#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
const int N=1e6+5;
int n,m;
LL r[N],d[N],s[N],t[N],c[N];
bool cheak(int mid){//判断第mid个申请是否可以满足
memset(c,0,sizeof(c));//每次都会有判断,防止上次的数据影响本次的判断
for(int i=1;i<=mid;i++){//采用申请人由0到差分数组,所以直接差分操作即可
c[s[i]]+=d[i];
c[t[i]+1]-=d[i];
}
int ans=0;
for(int i=1;i<=n;i++){//求前缀和,即还原数组
c[i]+=c[i-1];
if(c[i]>r[i]){//如果需要的教室大于所能提供的教室,则返回false
return false;
}
}
return true;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>r[i];
}
for(int i=1;i<=m;i++){
cin>>d[i]>>s[i]>>t[i];
}
int l=0,r=m;
while(l<r){//实行二分查找最大能满足的申请人编号
int mid=l+r+1>>1;//向上取整
if(cheak(mid))l=mid;
else r=mid-1;
}
if(r==m){//如果最大满足的编号等于m,说明所有订单均可满足
cout<<0<<endl;
}else{
cout<<-1<<endl<<r+1<<endl;//前面定义的为能满足的最大编号,r+1即为第一个不能满足的编号
}
return 0;
}
由此篇可见差分还是比较重要的,区间修改算法的效率也是非常高的,在算法竞赛中比较重要,希望对大家有所帮助,文章有错误的地方,恳请各位大佬指出。执笔至此,感触彼多,全文将至,落笔为终,感谢大家的支持。