【acwing 寒假每日一题】day8校门外的树

题目来源：校门外的树

题目描述

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

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

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

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

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

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

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

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

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

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

数据范围
1≤L≤10000,
1≤M≤100
输入样例：
500 3
150 300
100 200
470 471
输出样例：
298

思路

暴力做法

维护一个表示道路上是否种了树的bool数组 表示道路上的各个位置有没有种树 初始全部是true 每来一个区间 就将区间内所有的值(包括端点)置为false 最终输出bool数组的true的个数

区间合并

算法流程：

1. 将所有区间按左端点从小到大排序
2. 维护一个区间[ L ,R ]表示当前正在拓展的区间
3. 遍历所有区间，遍历到的区间记为[ l , r] ，将遍历到的区间去和我们正在拓展的区间比较
   2.1. l <=R 因为我们是将区间从小到大排序之后遍历的，那么此时表示我们遍历到的区间和我们正在拓展的区间一定存在交集，那么应该合并他们，左端点肯定是L不变，右端点取两者右端点的较大者
   2.2. l>R 表示当前遍历的区间和我们拓展的区间没有交集 应该将我们拓展的区间存起来 然后我们继续拓展这个遍历到的区间(即直接将这个遍历到的区间置为拓展区间)

代码

暴力法

O(NM)

#include<bits/stdc++.h>

using namespace std;

const int N=1e4+10;

int n,m;
bool st[N];


int main()
{
    cin>>n>>m;
    for(int i=0;i<=n;i++) st[i]=true;
    for(int i=0;i<m;i++)
    {
        int l,r;
        cin>>l>>r;
        for(int i=l;i<=r;i++) st[i]=false;
    }
    int cnt=0;
    for(int i=0;i<=n;i++) if(st[i]) cnt++;
    cout<<cnt<<endl;
    return 0;
}

区间合并

O(Nlog(N))（复杂度只要在排序）

#include<bits/stdc++.h>

using namespace std;

typedef pair<int,int> PII;

int main()
{
    int n,m;
    cin>>n>>m;
    vector<PII> segs;
    for(int i=0;i<m;i++)
    {
        int l,r;
        cin>>l>>r;
        segs.push_back({l,r});
    }
    sort(segs.begin(),segs.end());
    int st=segs[0].first,ed=segs[0].second;
    int res=0;
    for(auto& t:segs)
    {
        if(t.first>ed)
        {
            res+=ed-st+1;
            st=t.first,ed=t.second;
        }else{
            ed=max(ed,t.second);
        }
    }
    res+=ed-st+1;
    cout<<n+1-res<<endl;
    return 0;
}