Description
某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0，1，2，……，L，都种有一棵树。由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。
Input
输入第一行有两个整数L（1 <= L <= 10000）和 M（1 <= M <= 100），L代表马路的长度，M代表区域的数目，L和M之间用一个空格隔开。接下来的M行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。
Output
输出包括一行，这一行只包含一个整数，表示马路上剩余的树的数目。
Sample Input
500 3
150 300
100 200
470 471
Sample Output
298
解题思路：
(1)最直观的思路就是建立一个一维数组，用该数组来存放马路各位置点当前的状态：假设1代表当前位置的状态为有树，用0来表示当前位置的状态为地铁，根据题目所给的地铁区域，可以将对应的状态区域置0，最后当置0完题目所给的所有地铁段时，再重新对整条公路的状态遍历一遍，用一个记数变量记录状态为1的个数，即为所求。
ps:用数组的方式的优点就是直观好理解，缺点是费内存。当L很大的时候这种方式就不适用了。
int use_array(int L, int M)
{
int a[MAXSIZE];
int i,j,b,c,count = 0;
for(i = 0;i <= L; i++)
a[i] = 0;
for(i = 0; i < M; i++)
{
scanf("%d%d",&b,&c);
for( j = b; j <= c; j++)
{
a[j] = 1;
}
};
for( i = 0; i <= L;i++)
if(a[i] == 0)
count++;
return count;
}
(2)这里题中L为10000，当L为10^7或更大的时候，这种用一位数组的方式显然就不太适合了。我们可以考虑合并区域的方式。
设定一个数组a[m][2],装起点，终点。区域数为M，然后判断a[i][0]和a[i][1](第一段）,a[j][0],a[j][1]（第二段）的关系
有六种：分别用ABCD表示这四个数。
1，A>=C并B<=D.则把A,B,都设为0 （忽视掉第一段，因为此段与在第二段中）
2，A>=C B>=D.则A = C,B = B C =0 ,D = 0两段合为一段从长度C到B)
3，B<=D,则不变，(两者互补不干扰。)
4，A>=D ,不变，（两者互不干扰）
5，A<=C B>=D,则把 C, D 都设为0（忽视掉第二段，因为第二段在第一段中）
6，A<=C B<=D，则A =A B =D C =0 ,D = 0（两段合为一段，长度为A到D）
最后用二重循环比较，,比较完后每个数组的头减尾然后相加就是移走的数总长度（丢弃重合的），然后公路总长度减去就是移走的长度就是剩下数的数目。
int use_merger(int l,int m)
{
int i=0,j,count = 0,len = m;
int a[100][2];
while(len--)
{
scanf("%d %d",&a[i][0],&a[i][1]);
for(j = 0; j < i; j++)
{
if((a[i][0] >= a[j][0])&&(a[i][1]<=a[j][1]))
{
a[i][0] = a[i][1] = 0;
}
else if((a[j][0]<=a[i][0])&&(a[i][0]<=a[j][1])&&(a[i][1]>=a[j][1]))
{
a[i][0] = 0;
a[j][1] = a[i][1];
a[i][1] = 0;
}
else if((a[i][0] <= a[j][0])&&(a[i][1] >= a[j][1]))
{
a[j][0] = a[j][0] = 0;
}
else if((a[i][0] <= a[j][0])&&(a[j][0]<=a[i][1])&&(a[i][1] <= a[j][1]))
{
a[i][1] = 0;
a[j][0] = a[i][0];
a[i][0] = 0;
}
else if((a[i][0] <= a[j][0])&&(a[i][1] >= a[j][1]))
{
a[j][0] = a[j][0] = 0;
}
else if((a[i][1]<=a[j][0])||(a[i][0]>=a[j][1]))
{
NULL;
}
else
NULL;
}
i++;
}
for( i = 0; i < m; i++)
if(a[i][0]!=a[i][1])
count += (a[i][1] - a[i][0] + 1);
return count;
}
(3) 处理这类线段的问题，用线段树是最好的。http://baike.baidu.com/view/670683.htm点击打开链接，这里面有对线段树的详细介绍。这里就不用代码实现了。
头文件定义如下：
#include<stdio.h> #define MAXSIZE 10000
main函数如下：
int main()
{
int sum,m,l;
scanf("%d%d",&l,&m);
printf("\n用数组方式计算\n");
sum = use_array(l,m);
printf("%d\n",sum);
printf("\n用合并方式计算\n");
sum = use_merger(l,m);
printf("%d\n",l+1-sum);
return 0;
}
运行结果如下：