灬荣丶

用户名：uq_14130869763

访问量：2927

签　名：

等　　级
排　　名	459
经　　验	4601
参赛次数	4
文章发表	2
年　　龄	0
在职情况	学生
学　　校	内蒙古大学
专　　业

　　自我简介：

TA的其他文章

校门外的树-19行代码-时间复杂度O(n) !
浏览：2135

从O(n)到O(m)--从差分到扫描线
浏览：485

你可能喜欢

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

从O(n)到O(m)--从差分到扫描线

　　作者: 灬荣丶　　　　发表时间：2022-01-11 15:58:17 浏览：485　|　评论：0　

原题链接：校门外的树

##### 用差分的方法可以实现时间复杂度O(n)，这里使用扫描线，可以实现更快时间复杂度O(m)！
### 解题思路:
######   与差分数组这里不同的是这里要使用c++内部的map容器。
######让每个区间的两端点在对应容器 a[] 上赋值，使左右端点的值为相反数；
###### 数组初始为0，flag等于0;
###### 从前到后遍历整个路段, 若是到一个左端点flag就会增加（或者减少），直到右端点，会重新变回 0,所以在flag == 0 的时候代表该下标有树，这样可以实现时间复杂度为O（n）。

### 优化：
#####   这段路有500米，但端点只有6个，一下运行500次是不是浪费时间了。
##### 我们每次修改两端点就可以实现差分，那我们可不可以只遍历所有端点来完成统计树的数量。
我们每到一个端点都会修改flag的值。而当我们的flag > 0时，从**当前端点开始一直到下一个端点这其中的路程**就是**移走的树**的数量。依次累加所有的区间。

正如区间<4-18>和<7-20>;正如区间<4-18>和<7-20>;

a[4] = 1,a[18] = -1; a[7] = 1,a[20] = - 1;    
这里就只需要遍历四个点就行了，可以看出**移走的树**的数量 ****ans = 7 - 4 + 18 - 7 + 20 - 18******；	
 ![图解](/image_editor_upload/20210221090016_15443.png "图解")

### 参考代码:
```c++
#include <bits/stdc++.h>
using namespace std;

map<int,int> a;
int main() {
    int l, m, x, y, ans = 0, flag = 0;
    scanf("%d%d",&l,&m);
    for(int i = 0; i < m; i++){
        scanf("%d%d",&x,&y);
        a[x]++;//左端点为正
        a[y+1]--;//右端点为负，只有两个都遍历到flag变为0
    }
    int last;
    for(auto& x : a){//x.first是下标，x.second是差分值
        if(flag > 0) ans += x.first - last;
        flag += x.second;
        last = x.first;
    }
    ans = l + 1 - ans;
    printf("%d\n",ans);
}
```

**n范围到10000，O（n）要运行10000次,但O(m)最多运行600次**

0.0分

10 人评分

C语言网推出会员服务，提供C/C++/算法/Python等多套视频学练课程+源码资源社群答疑+私活推荐等资源，享受丰富的技术学习到变现的乐趣，以含金量和学习效果勇敢挑战同类辅导！点击了解开通

灬荣丶

TA的其他文章

你可能喜欢

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

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

C语言训练-计算1~N之间所有奇数之和（C语言代码）

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

C语言训练-自由落体问题（C语言代码）

从O(n)到O(m)--从差分到扫描线

评论区

精彩推荐

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

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

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

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

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

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

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

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

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

P1002 （C++代码）

灬荣丶

TA的其他文章

你可能喜欢

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

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

C语言训练-计算1~N之间所有奇数之和 （C语言代码）

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

C语言训练-自由落体问题 （C语言代码）

从O(n)到O(m)--从差分到扫描线

评论区

精彩推荐

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

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

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

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

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

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

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

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

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

P1002 （C++代码）

C语言训练-计算1~N之间所有奇数之和（C语言代码）

C语言训练-自由落体问题（C语言代码）

　　评论区

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