描述 有一个长度为整数L(1<=L<=10000)的马路,可以想象成数轴上长度为L的一个线段,起点是坐标原点,在每个整数坐标点有一棵树,即在0,1,2,...,L共L+1个位置上有L+1棵树。 现在要移走一些树,移走的树的区间用一对数字表示,如 100 200表示移走从100到200之间(包括端点)所有的树。 可能有M(1<=M<=100)个区间,区间之间可能有重叠。现在要求移走所有区间的树之后剩下的树的个数。用c++
时间: 2024-04-09 19:28:32 浏览: 128
这是一个经典的区间覆盖问题。下面是一个示例的C++代码,用于计算移走所有区间的树之后剩下的树的个数:
```cpp
#include <iostream>
#include <vector>
using namespace std;
int main() {
int L, M;
cin >> L >> M;
vector<int> trees(L + 1, 1); // 初始化所有位置都有树
for (int i = 0; i < M; i++) {
int start, end;
cin >> start >> end;
for (int j = start; j <= end; j++) {
trees[j] = 0; // 将区间内的树移走
}
}
int remainingTrees = 0;
for (int i = 0; i <= L; i++) {
if (trees[i] == 1) {
remainingTrees++;
}
}
cout << remainingTrees << endl;
return 0;
}
```
你可以将上述代码保存为一个名为 "main.cpp" 的文件,并编译运行来测试它。需要注意的是,输入的格式应该符合题目描述中所提到的格式。
希望这能帮到你!如果有任何其他问题,请随时向我提问。
阅读全文