题目描述
某校大门外长度为L的马路上有一排树,每两棵相邻的树之间的间隔都是1米。
我们可以把马路看成一个数轴,马路的一端在数轴0的位置,另一端在L的位置;数轴上的每个整数点,即0,1,2,……,L,都种有一棵树。
由于马路上有一些区域要用来建地铁。
这些区域用它们在数轴上的起始点和终止点表示。
已知任一区域的起始点和终止点的坐标都是整数,区域之间可能有重合的部分。
现在要把这些区域中的树(包括区域端点处的两棵树)移走。
你的任务是计算将这些树都移走后,马路上还有多少棵树。
样例
输入样例:
500 3
150 300
100 200
470 471
输出样例:
298
算法1
(朴素做法) $O(ML)$
直接枚举
时间复杂度
参考文献
C++ 代码
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
bool st[N];
int n, m;
int main(){
cin >> n >> m;
int a, b;
for (int i = 0; i < m; i ++){
cin >> a >> b;
for (int i = a; i <= b; i ++) st[i] = 1;
}
int res = 0;
for (int i = 0; i <= n; i ++) res += !st[i];
cout << res << endl;
return 0;
}
算法2
(区间合并) $O(n)$
区间合并模板题。
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
const int N = 100010;
PII a[N];
int n, m;
int main(){
cin >> n >> m;
for (int i = 0; i < m; i ++) cin >> a[i].first >> a[i].second;
sort(a, a + m);
int l = a[0].first, r = a[0].second;
int sum = 0;
for (int i = 1; i < n; i ++)
if (a[i].first <= r) r = max(a[i].second, r);
else {
sum += r - l + 1;//注意这里是合并上一次区间的结果
l = a[i].first, r = a[i].second;
}
sum += r - l + 1;//因此出了for循环,需要将最后一次合并的结果加进来
cout << n + 1 - sum << endl;
return 0;
}
sort 又是是什么意思?
const int 是什么意思?
还有bool 是什么意思?
大佬求抱!