HRBUST

首先读题，题意很清晰明了，就是把从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 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

李嘉

为什么要a[0]=c[0]; 不应该是原数组的值赋给差分数组吗，还有为什么要放到修改完数组再赋给第一个值，而不是一开始就进行赋值

2023-09-26 21:23:29

sor

9个头文件，啥个意思？

2021-11-02 23:09:26

HRBUST

TA的其他文章

你可能喜欢

【密码】（C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

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

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

【金明的预算方案】（C++代码）

字符串比较（C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

【计算两点间的距离】（C语言代码）

蓝桥杯基础练习VIP-报时助手（C++代码）

母牛的故事（java语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C++代码）

C语言训练-求车速（C语言代码）

1169题解

HRBUST

TA的其他文章

你可能喜欢

【密码】 （C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

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

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

【金明的预算方案】 （C++代码）

字符串比较 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

【计算两点间的距离】 （C语言代码）

蓝桥杯基础练习VIP-报时助手 （C++代码）

母牛的故事 （java语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C++代码）

C语言训练-求车速 （C语言代码）

1169题解

【密码】（C语言代码）

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

　　评论区

【金明的预算方案】（C++代码）

字符串比较（C语言代码）

【计算两点间的距离】（C语言代码）

蓝桥杯基础练习VIP-报时助手（C++代码）

母牛的故事（java语言代码）

C语言训练-求车速（C语言代码）