方法一:暴力模拟法
-
开辟一个长度为 L + 1 的 bool 数组,每个元素代表树的状态: true: 有树, false:没有树。
-
遍历每条地铁,把地铁区间内的树砍掉,即对应数组元素置为 false。
-
统计数组中还有多少个 true ,就是还是剩多少棵树。
//cpp
#include <iostream>
using namespace std;
const int N = 10010;
bool tree[N];//保存树的数组
int main()
{
int l, m;
cin >> l >> m;
for(int i = 0; i<= l; i++) tree[i] = true;//路区间内有树,a[i] :true
while(m--)
{
int st, end;
cin >> st >> end;
for(int i = st; i <= end; i++) tree[i] = false;//地铁覆盖区间,a[i]:false
}
int res = 0;
for(int i = 0; i <= l; i++) res += tree[i];//统计还剩多少树。
cout << res;
}
方法二:区间合并
1. 将要砍掉树的区间合并在一起,合并后的区间没有重合部分。例如:[1~3]和[3~5] 合并成 [1~5]。
2. 数的总数 - 合并后所有区间覆盖的点数 = 剩余树的数量。
区间合并:
1. 将区间按左端点升序排序。
2. 从第一个区间开始,如果该区间的右端点大于后面相邻区间的左端点,当前区间右端点更新为:该区间右端点和相邻区间右端点最大值。直到不能继续合并,然后开始后面区间合并。
//cpp
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int n, m;
pair<int, int> undg[N];//存储地铁区间
int main()
{
cin >> n >> m;
int res = n + 1;
for(int i = 0; i < m; i++ ) cin >> undg[i].first >> undg[i].second;
sort(undg,undg + m);//按照左端点排序
int st = undg[0].first, ed = undg[0].second;//起始区间
for(int i = 1; i < m; i++)
{
if(ed >= undg[i].first) ed = max(ed, undg[i].second);//的右端点大于后面相邻区间的左端点,合并在一起
else// 否则重新开始合并
{
res -= ed - st + 1;//减去当前区间的树的数量
st = undg[i].first;//新维护区间的左端点
ed = undg[i].second;//新维护区间的右端点
}
}
res -= ed - st + 1;//减去最后一个地铁区间的树木
cout << res<< endl;
}
有问题可以直接评论~
觉得不错,可以点个赞~
模拟不错,简单易懂hh
sort 对pair排序是默认的按第一个元素排序吗
对