美食网站建设页面要求,政务网站建设目标和核心功能,百度站长工具网站提交,专题学习网站开发流程个人主页#xff1a;摆烂小白敲代码 创作领域#xff1a;算法、C/C 持续更新算法领域的文章#xff0c;让博主在您的算法之路上祝您一臂之力 欢迎各位大佬莅临我的博客#xff0c;您的关注、点赞、收藏、评论是我持续创作最大的动力 差分算法是一种在计算机科学中常用的算法… 个人主页摆烂小白敲代码 创作领域算法、C/C 持续更新算法领域的文章让博主在您的算法之路上祝您一臂之力 欢迎各位大佬莅临我的博客您的关注、点赞、收藏、评论是我持续创作最大的动力 差分算法是一种在计算机科学中常用的算法特别是在处理序列数据时它可以帮助我们快速计算出序列中相邻元素的差值。时间复杂度可以达到O(1)在C中实现差分算法不仅可以提高程序的效率还可以简化代码的复杂度。本文将详细介绍差分算法的原理、C实现方法以及算法例题。 算法原理
上一篇博客一篇带你速通前缀和算法C/C-CSDN博客我们介绍了前缀和算法这一篇文章就与前缀和算法相反为差分算法。
一维差分
差分算法的核心思想是利用已有的数据序列通过计算相邻元素之间的差值来生成一个新的序列。对于一个给定的序列 a[a1,a2,...,an]其差分序列 d 可以表示为d[i]a[i]−a[i-1]。差分数组长度一般为原定序列长度1即lenn1。其中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]cd[r1]-c这样我们再利用前缀和还原便可以得到原数组修改后的值。在还原时只需要将前i位差分数组相加便可以得到原数组比如还原第三位a[3]d[1]d[2]d[3]便可以还原其值其还原的第n1位一定是0。
我们设原数组序列为 a[3,1,5,4,2]设d为差分数组在[2,4]区间上的值统一2下面我们将模拟实现。
初始化 差分实现
我们需要在[2,4]区间上的值统一2那么转换为差分数组d[l]cd[r1]-cd[2]2d[41]-2。我们代入到过程实现一下。 原数组序列为 a[3,1,5,4,2]在[2,4]区间上的值统一2我们将得到a[3,3,7,6,2]与差分还原的来是一样的。 二维差分
前面我们讲述的是一维差分其数组为一维的其模型可以抽象为线性的。那么有些时候需要我们使用二维差分当题目出现矩阵时说明就涉及到了二维差分其模型可以抽象为矩阵二维差分稍微比一维差分难一点主要是在处理区间更新时。我们设d[i][j]为11点到ij点的差分子矩阵1xi,1yj,此时我们设a[i][j]Σd[i][j]1xi,1yj即a[i][j]差分矩阵的和。 构造差分矩阵
当我们需要构造差分数组实现修改区间的值时此时的递推关系式不再是跟一维差分相同由于是二维的所以转化为在一个矩阵上c在一个矩阵上-c那么如何确定这两个矩阵。假设我们在x1,y1-(x2,y2)这个矩阵统一加C那么转化为差分矩阵的操作为
d[x1][y1]C
d[x1][y21]-C
d[x21][y1]-C
d[x21][y21]C//上面操作等价于
for(int ix1;ix2;i)for(int jy1;jy2;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][y21] c;
}
构造差分矩阵解释
d[x1][y1]C相当于原矩阵A矩阵黄色每个值都C
d[x21][y21]C相当于整个矩阵ABCD矩阵每个值都C
此时A矩阵2C,B矩阵C,C矩阵CD矩阵C,我们再设法把不需要的减掉。
d[x1][y21]-C相当于AB矩阵黄色绿色都-C
此时A矩阵C,B矩阵0,C矩阵CD矩阵C,我们再设法把不需要的减掉。
d[x21][y1]-C相当于AC矩阵黄色蓝色都-C
此时A矩阵0,B矩阵0,C矩阵0,D矩阵C,达到了我们所需要的x1,y1到x2,y2加C的目的。 最后就是还原其值利用前缀和的思想如上图所示要求11-x2,y2的值那么可以转化为矩阵11-x2,y2-1与11-x2-1,y2的和减去11-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];}}
代码实现
#includeiostream
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][y21] 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; in; i){for(int j 1; jn; j){d[i][j] d[i][j-1] d[i-1][j] - d[i-1][j-1];printf(%d , d[i][j]);}coutendl;}return 0;
}算法例题
AcWing 4262. 空调
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..51 3 3 3 2
升高牛棚 2..51 4 4 4 3
升高牛棚 2..51 5 5 5 4
降低牛棚 3..41 5 4 4 4
降低牛棚 3..41 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的值即可 AC代码
#includeiostream
using namespace std;
const int N1e55;
int n,ans;
int p[N],t[N];//p数组既作为p数组又作为差分数组
int main(){cinn;for(int i1;in;i){cinp[i];}for(int i1;in;i){cint[i];p[i]-t[i];}//差分p[i]p[i]-p[i-1],差分数组边界p[1]p[1],p[n1]-p[n]for(int in1;i1;i--){//因为i要先于i-1更新所以逆序遍历p[i]-p[i-1];}for(int i1;in1;i){//只要遍历大于0或者小于零的p[i]累加即可if(p[i]0){ansp[i];}}coutansendl;return 0;
} AcWing 4862. 浇花
某公司养有观赏花这些花十分娇贵每天都需要且仅需要浇水一次。
如果某一天没给花浇水或者给花浇水超过一次花就会在那一天死亡。
公司即将迎来 n 天假期编号 1∼n。
为了让花能够活过整个假期公司领导安排了 m 个人编号 1∼m来公司浇花其中第 i 个人在第 [ai,bi] 天每天来公司浇一次花。
领导是按照时间顺序安排的浇花任务保证了对于 1≤i≤m−1均满足bi≤ai1。
给定领导的具体安排请你判断花能否活过整个假期如果不能请你输出它是在第几天死的以及那一天的具体浇水次数。
输入格式
第一行包含两个整数 n,m。
接下来 m 行每行包含两个整数 ai,bi。
输出格式
输出一行结果。
如果花能活过整个假期则输出 OK。
如果花不能活过整个假期则输出两个整数 x,y表示花是在第 x 天死的这一天花被浇了 y 次水。
数据范围
前 4 个测试点满足 1≤n,m≤10。 所有测试点满足 1≤n,m≤10^51≤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 解题思路
这道题其实一眼看上去是区间合并问题这里我们讲解的差分算法那么我们就用差分解决此题。员工在一个区间内浇水那么就可以视为区间修改可以构造差分数组快速解决这道题还一个条件就是花不能多浇水这个实现也可以在差分数组之中我们可以利用前缀和还原差分数组得到此朵花被浇了几次水进而判断此花是否存活。 AC代码
#includeiostreamusing 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;
} AcWing 503. 借教室
在大学期间经常需要租借教室。
大到院系举办活动小到学习小组自习讨论都需要向学校申请借教室。
教室的大小功能不同借教室人的身份不同借教室的手续也不一样。
面对海量租借教室的信息我们自然希望编程解决这个问题。
我们需要处理接下来 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即为不能满足的订单上代码。 AC代码
#includeiostream
#includecstring
using namespace std;
typedef long long LL;
const int N1e65;
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 i1;imid;i){//采用申请人由0到差分数组所以直接差分操作即可c[s[i]]d[i];c[t[i]1]-d[i];}int ans0;for(int i1;in;i){//求前缀和即还原数组c[i]c[i-1];if(c[i]r[i]){//如果需要的教室大于所能提供的教室则返回falsereturn false;}}return true;
}
int main(){cinnm;for(int i1;in;i){cinr[i];}for(int i1;im;i){cind[i]s[i]t[i];}int l0,rm;while(lr){//实行二分查找最大能满足的申请人编号int midlr11;//向上取整if(cheak(mid))lmid;else rmid-1;}if(rm){//如果最大满足的编号等于m说明所有订单均可满足cout0endl;}else{cout-1endlr1endl;//前面定义的为能满足的最大编号r1即为第一个不能满足的编号}return 0;
} 由此篇可见差分还是比较重要的区间修改算法的效率也是非常高的在算法竞赛中比较重要希望对大家有所帮助文章有错误的地方恳请各位大佬指出。执笔至此感触彼多全文将至落笔为终感谢大家的支持。
