[NOIP2005]校门外的树

思路

一开始有l+1棵树,刨去所给范围合并所得后所得的树的个数就是结果。
用一个vis数组来记录刨去树的区间(是一个闭区间),
数据范围很小,暴力可解。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e4+7;

int main(){
    int l,m,x,y,vis[maxn]={0},cnt=0;
    scanf("%d%d",&l,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&x,&y);
        for(int i=x;i<=y;i++){
            if(!vis[i]){
                vis[i]=1;
                cnt++;
            }
        }
    }
    cout<<l-cnt+1<<endl;
    return 0;
}