校门外的树

题目 校门外的树

image-4b75221d

思路分析

是模版的变形

也可以作为 农田灌溉 管道 无线网络 这三题的一个引入

可以用标记的方式 遍历标记查看数目 也可以用区间合并

https://www.acwing.com/solution/content/193960/

这篇还给出了线段树、树状数组等方式的解答 等以后学到了回过头来看一下

要注意几个点

0~400 401~500

这一段是可以合并的 与模版有些不同

所以要把不合并的条件修改为 ed+1<road.first

其次注意一个计数问题

1~2 是2-1+1棵树

所以每个区间应该是 r-l+1棵

其他没什么了

代码实现

原模板stl 19ms

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

typedef pair<int,int> PII;

vector<PII> roads;

int L,M;

int main()

{

    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

    cin>>L>>M;

    for(int i=0;i<M;i++){

        int l,r;

        cin>>l>>r;

        roads.push_back({l,r});

    }

    sort(roads.begin(),roads.end());

    int st=-100,ed=-100;

    int res=0;

    for(auto road:roads){

        if(ed+1<road.first){

            if(ed!=-100)

                res+=ed-st+1;

            st=road.first,ed=road.second;

        }

        else if(ed<road.second)

            ed=road.second;

    }

    if(ed!=-100)

        res+=ed-st+1;

    cout<<(L+1)-res<<endl;

    return 0;

}

优化模板 14ms

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

const int N=100010;
typedef pair<int,int> PII;
PII roads[N];
int cnt=0;
int L,M;

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>L>>M;
    for(int i=0;i<M;i++){
        int l,r;cin>>l>>r;
        roads[cnt++]={l,r};
    }
    sort(roads,roads+M);

    int st=-100,ed=-100;
    int res=0;
    for(int i=0;i<M;i++){
        if(ed+1<roads[i].first){
            if(ed!=-100)    res+=ed-st+1;
            st=roads[i].first,ed=roads[i].second;
        }
        ed=max(roads[i].second,ed);
    }
    if(ed!=-100)    res+=ed-st+1;
    cout<<(L+1)-res<<endl;
    return 0;
}

同类题型

视频讲解

⬅️ 救生员 🏠 00-刷题理模型 ➡️ 管道