【每日一题】DAY8——校门外的树

题目描述

某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是 1 米。

我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在 L 的位置；数轴上的每个整数点，即 0，1，2，……，L，都种有一棵树。

由于马路上有一些区域要用来建地铁。

这些区域用它们在数轴上的起始点和终止点表示。

已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。

现在要把这些区域中的树（包括区域端点处的两棵树）移走。

你的任务是计算将这些树都移走后，马路上还有多少棵树。

输入格式

输入文件的第一行有两个整数L和M，L代表马路的长度，M代表区域的数目，L和M之间用一个空格隔开。

接下来的M行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。

输出格式

输出文件包括一行，这一行只包含一个整数，表示马路上剩余的树的数目。

数据范围

1 ≤ L ≤ 10000 1≤L≤10000 1≤L≤10000
1 ≤ M ≤ 100 1≤M≤100 1≤M≤100

输入样例：

500 3
150 300
100 200
470 471

输出样例：

298

思路

这道题有多种解法，这里我们使用两种：

第一种：暴力模拟法

1. 开辟一个长度为 L + 1 的 bool 数组，每个元素代表树的状态: true: 有树， false：没有树。
2. 遍历每条地铁，把地铁区间内的树砍掉，即对应数组元素置为 false。
3. 统计数组中还有多少个 true ,就是还是剩多少棵树。

#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]和[35] 合并成 [1~5]。
2. 数的总数 - 合并后所有区间覆盖的点数 = 剩余树的数量。

区间合并：

1. 将区间按左端点升序排序。
2. 从第一个区间开始，如果该区间的右端点大于后面相邻区间的左端点，当前区间右端点更新为：该区间右端点和相邻区间右端点最大值。直到不能继续合并，然后开始后面区间合并。

#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;
}