[NOIP2005]校门外的树 这道题是noip2005的一道真题，好了，我们一起来看看题意吧：
题目描述
某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0，1，2，……，L，都种有一棵树。 由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。
输入描述
第一行有两个整数：L（1 <= L <= 10000）和 M（1 <= M <= 100），L代表马路的长度，M代表区域的数目，L和M之间用一个空格隔开。接下来的M行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。
输出描述
包括一行，这一行只包含一个整数，表示马路上剩余的树的数目。
示例1
输入
500 3
150 300
100 200
470 471
输出
298
题目链接： [NOIP2005]校门外的树
思路:
我们可以算出哪些区域是建地铁的，最后计算没有建地铁的就是答案，这道题我们可以采用差分，区间合并，离散化等方法来做，接下来我就展示三种方法吧
我们来看看成功AC的代码吧：
解法1： 差分
#include<bits/stdc++.h> using namespace std; int l,m; int a[100010],b[100010]; int ans=0; int main(){ ios::sync_with_stdio(false); cin>>l>>m; for(int i=1;i<=l;i++) b[i]=a[i]-a[i-1]; while(m--){ int x,y; cin>>x>>y; b[x]=b[x]+1;b[y+1]=b[y+1]-1; //在 x,y之间建地铁 a数组对应的会增加 } for(int i=0;i<=l;i++){ a[i]=b[i]+a[i-1]; if(a[i]==0) ans++;//a数组为0表示这里还有树 } cout<<ans; return 0; }
解法2： 区间合并
#include<bits/stdc++.h> using namespace std; int n,m; struct ed{ int x,y; }a[100010]; bool cmp(ed x,ed y){ return x.x<y.x; } int main(){ cin>>n>>m; for(int i=1;i<=m;i++){ int x,y; cin>>x>>y; a[i]={x,y}; } sort(a+1,a+m+1,cmp); int cnt=0; int l=a[1].x,r=a[1].y; for(int i=2;i<=m;i++){ if(a[i].x<r){ r=max(r,a[i].y); }else{ cnt+=(r-l+1); l=a[i].x; r=a[i].y; } } cnt+=(r-l+1); cout<<n-cnt+1; return 0; }
解法3： 离散化与区间合并
#include<bits/stdc++.h> using namespace std; int n,m; struct ed{ int x,y; }a[100010]; bool cmp(ed x,ed y){ return x.x<y.x; } int main(){ cin>>n>>m; for(int i=1;i<=m;i++){ int x,y; cin>>x>>y; a[i]={x,y}; } sort(a+1,a+m+1,cmp); int cnt=0; int l=a[1].x,r=a[1].y; for(int i=2;i<=m;i++){ if(a[i].x<r){ r=max(r,a[i].y); }else{ cnt+=(r-l+1); l=a[i].x; r=a[i].y; } } cnt+=(r-l+1); cout<<n-cnt+1; return 0; }
