时间限制: 1Sec 内存限制: 128MB
题目描述
某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0，1，2，……，L，都种有一棵树。由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。
输入
输入的第一行有两个整数L（1 <= L <= 10000）和 M（1 <= M <= 100），L代表马路的长度，M代表区域的数目，L和M之间用一个空格隔开。接下来的M行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。
输出
输出包括一行，这一行只包含一个整数，表示马路上剩余的树的数目。
样例输入
500 3
150 300
100 200
470 471
样例输出
298
解法一：暴力回溯（时间复杂度n^2）
解题思路：
由于每一次输入的区间都有可能与之前输入的区间存在交集，通过两层循环对所有区间进行排异，获得互不相交的区间，这样将总区间中的树数量减去处理后的区间中的树的数目，就是马路上剩余的树的数目。
代码
#include<stdio.h>
typedef struct schooltree
{
int start;
int end;
}schooltree;
int intersection(int *paststart,int *pastend,int *nextstart,int *nextend){
if(*nextend>=*paststart&&*nextend<=*pastend&&*nextstart<=*paststart) *nextend=*paststart-1;
if(*nextend>=*paststart&&*nextend<=*pastend&&*nextstart>*paststart) {*nextstart=0;*nextend=0;}
if(*nextend>*pastend&&*nextstart<=*paststart) {*paststart=0;*pastend=0;}
if(*nextend>*pastend&&*nextstart>*paststart&&*nextstart<=*pastend) *nextstart=*pastend+1;
return 0;
}
int main(){
int len,treenum;
int result=0;
scanf("%d %d",&len,&treenum);
schooltree st[treenum];
for(int i=0;i<treenum;i++){
scanf("%d %d",&st[i].start,&st[i].end);
}
for(int i=1;i<treenum;i++){
for(int j=0;j<i;j++){
if((st[j].start==0&&st[j].end==0)||(st[i].start==0&&st[i].end==0)) continue;
else intersection(&st[j].start,&st[j].end,&st[i].start,&st[i].end);
}
}
for(int i=0;i<treenum;i++){
if(st[i].start==0&&st[i].end==0) result=result+0;
else result+=st[i].end-st[i].start+1;
}
result=len+1-result;
printf("%d",result);
return 0;
}
解法二：差分法（时间复杂度n）
解题思路:
让每个区间的两端点在对应数组 a[] 上赋值，使左右端点的值为相反数；
i 从 0 到 l 开始遍历, 若是到一个左端点flag就会增加（或者减少），直到右端点，会重新变回 0,所以遍历中只有flag等于0的时候ans++；
#### 正如区间<4-18>和<7-20>;正如区间<4-18>和<7-20>;
#### a[4] = 1,a[18] = -1; a[7] = 1,a[20] = - 1;
#### 可以看出在<4-18>与<7-20> 内flag 不等于 0；
代码：
#include <stdio.h>
int a[10005];
int main() {
int x, y, l, m, i, ans = 0, flag = 0;
scanf("%d%d",&l,&m);
for(i = 1; i <= m; i++){
scanf("%d%d",&x,&y);
a[x]++;//左端点为正
a[y]--;//右端点为负，只有两个都遍历到flag变为0
}
for(i = 0; i <= l; i++){
if(a[i] != 0){
flag += a[i];
continue;//若不结束，右端点可能被计入ans
}
if(flag == 0)ans++;
}
printf("%d\n",ans);
}
