校门外的树

给定范围，给一些区间，这些区间树被清理掉，问最后剩多少种树。

方法一，预处理标记该点已不存在树。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5;
int vis[maxn];
int main(){
    int l,r,n,m,sum=0;cin>>n>>m;
    for(int i=0;i<m;i++){
        cin>>l>>r;
        for(int j=l;j<=r;j++)vis[j]=1;
    }
    for(int i=0;i<=n;i++){if(!vis[i])sum++;}
    cout<<sum<<endl;
    return 0;
}

方法二，利用区间有树，则第一个点权值+1,最后一个点的后一个点-1，利用前缀和是否为0，判断是该点是否有树。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5;
int a[maxn];
int sum;
int main(){
    int n,m,l,r;cin>>n>>m;
    for(int i=0;i<m;i++){
        scanf("%d%d",&l,&r);
        a[l]++;a[r+1]--;
    }
    int ans=0;
    for(int i=0;i<=n;i++){
        sum+=a[i];
        if(!sum)ans++;
    }
    cout<<ans<<endl;
    return 0;
}

原文链接: https://www.cnblogs.com/mohari/p/12984394.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/351345

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

校门外的树

相关推荐