简单易懂应对多次操作的差分组解法

667 阅读 4 评论 0 点赞

这道题我做过很多次了。。。
各种各样的变种，决定总结一下

首先读题，题意很清晰明了，就是把从a到b的树砍光，之后反复重复m次，每次的a，b都会变化
因此第一种朴素的想法诞生了。。。
将有树的位置用数组标记为0，一但进行砍伐活动，就将从a到b的所有数都加上1
最后一次砍伐结束后去遍历数组，看数组中有几个0
例子：
数组a一开始初始化全为0
第一次砍伐1-3
a[0] a[1] a[2] a[3] a[4] a[5] ...
  0    1    1    1    0    0

第二次砍伐2-5
a[0] a[1] a[2] a[3] a[4] a[5] ...
  0    1    2    2    1    1
 
依次类推
解法一的代码
```cpp
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <map>
#include <queue>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int l,r,m,len,ans;
int i,j;
int a[10005],c[10005];
int main()
{
    cin>>len>>m;
    for(i=1;i<=m;i++)
    {
        cin>>l>>r;
        for(j=l;j<=r;j++) a[j]++;
    }

for(i=0;i<=len;i++)
    {
        if(a[i]==0) ans++;
    }
    cout<<ans<<endl;
    return 0;
}

```

这种方法很好理解，编写过程也较为简单，但我并不建议这样解决问题，因为这道题的数据范围很小 m竟然只有100！！！

这道题的变种m往往会达到一个极大的数值比如1000000或者更多，在这种情况下上面的方法就会超时因为询问的次数过多，同时每次从a到b遍历赋值的过程过于繁琐
对这道题进行更加深入的分析，可以发现实质进行的操作是在对一个区间的所有数进行加减操作，这个操作可以使用线段树实现，但是在这道题中，可以使用差分组进行运算
差分数组指的是当前数组与前一个数组进行做差，并储存在新的数组中
公式即 c[i]=a[i]-a[i-1]（公式不唯一）

例子：
a[i] 0 0 0 0 0
c[i] 0 0 0 0 0

砍伐1-3
a[i] 0 1 1 1 0
c[i] 0 1 0 0 -1

从这个例子可以看出在对一个区间进行加减操作时只需要变化c[a]和c[b+1] 即可
在得出变化后的差分组后，可反向推导公式
a[i]=c[i]+a[i-1]
只需要遍历一次就可以解决问题，成倍的提高效率。。。

```cpp
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <map>
#include <queue>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int l,r,m,len,ans;
int i,j;
int a[10005],c[10005];
int main()
{
    cin>>len>>m;
    for(i=1;i<=m;i++)
    {
        cin>>l>>r;
        c[l]++;
        c[r+1]--;
    }

a[0]=c[0];
    for(i=1;i<=len;i++)
    {
        a[i]=a[i-1]+c[i];
    }

for(i=0;i<=len;i++)
    {
        if(a[i]==0) ans++;
    }

cout<<ans<<endl;
    return 0;
}

```

0.0分

5 人评分

本文分类：题解列表
浏览次数：667 次浏览
发布日期：2021-04-13 21:54:29
本文链接：https://blog.dotcpp.com/a/78530

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

简单易懂应对多次操作的差分组解法

评论列表共有 4 条评论

发表评论取消回复

简单易懂 应对多次操作的差分组解法

数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)

点进来你会后悔的

简简单单的循环

简单的回文数

评论列表 共有 4 条评论

发表评论 取消回复

简单易懂应对多次操作的差分组解法

评论列表共有 4 条评论

发表评论取消回复