问题描述：
某校大门外长度为 L 的马路上有一排树，每两棵相邻的树之间的间隔都是1 米。我们
可以把马路看成一个数轴，马路的一端在数轴0 的位置，另一端在L 的位置；数轴上的每
个整数点，即0，1，2，……，L，都种有一棵树。
由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已
知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些
区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上
还有多少棵树。
输入数据：
输入的第一行有两个整数L（1 <= L <= e9）和 M（1 <= M <= 100），L 代表马路
的长度，M 代表区域的数目，L 和M 之间用一个空格隔开。接下来的M 行每行包含两个不
同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。
输出要求：
输出包括一行，这一行只包含一个整数，表示马路上剩余的树的数目。
输入样例：
500 3
150 300
100 200
470 471
输出样例:
298

[ 本帖最后由 书呆 于 2010-3-26 18:50 编辑 ]

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct _pos{
    int start;
    int end;
}pos;

int main(void)
{
    int L, M;
    int i, j, cnt = 0;
    int *Lary;
    pos *Mary;

    scanf("%d%d", &L, &M);

    Lary = (int *)malloc(sizeof(int)*(L+1));
    Mary = (pos *)malloc(sizeof(pos)*M);

    memset(Lary, 0, sizeof(int)*L);
    for (i = 0; i < M; i ++)
    {
        scanf("%d%d", &Mary[i].start, &Mary[i].end);
        for (j = Mary[i].start; j <= Mary[i].end; j ++)
        {
            Lary[j] ++;
        }
    }
    for (i = 0; i <= L; i ++)
    {
        if (Lary[i] == 0) cnt ++;
    }
    printf("%d\n", cnt);                                                                                          
    free(Lary);                                                                                                   
    free(Mary);                                                                                                   
}
程序我没有做输入的数的检查，默认输入的数都是合法的(程序不用数组Mary也行，输入时直接用两个变量start，end代替就可以了)


[ 本帖最后由 ldg628 于 2010-3-26 17:28 编辑 ]

回复 2楼 ldg628
请注意L的范围(1 <= L <= e10)

这个还要我帮添呀。。囧。。。
在语句scanf("%d%d", &L, &M);下添加下面的代码，头文件要加上#include <math.h>
    if (L < 1 || L > pow(10,10) || M < 1 || M > 100)
    {
        printf("Override!\n");
        return 1;
    }

(int *)malloc(sizeof(int)*(L+1));
你不觉得你开的数组太过了吗？e10 啊！38G！

L的取值修改为 1<= L<=e9 , int表示范围之内，怎么办呢？
ldg628 的方法只是当L值很小的时侯可用，L很大时，就不行了

想省空间可以用位来操作，一个位代表一个数组元素，不申请那么大的空间，处理就麻烦些，空间换时间，如果实在太大了，就要另想办法

随手写的，没有考虑那么周全，不好意思～～～

#include <stdio.h>
#include <stdlib.h>

typedef struct _pos{
    int s;
    int e;
}pos;
int Judge(pos e, pos cur)  //判断两条线段是否相交
{
    int ret;
    if (e.s < cur.s)
    {
        if (cur.s > e.e)
            ret = 0;
        else
            ret = 1;
    }else
    {
        if (e.s > cur.e)
            ret = 0;
        else
            ret = 1;
    }
    return ret;
}
void Join(pos *ary, int n)
{
    int i, j;
    for (i = 0; i < n; i ++)
    {
        for (j = i+1; j < n; j ++)
        {
            if (ary[j].s == -1) continue;
            if (Judge(ary[i], ary[j]))
            {
                ary[i].s = (ary[i].s < ary[j].s)?ary[i].s:ary[j].s;
                ary[i].e = (ary[i].e > ary[j].e)?ary[i].e:ary[j].e;
                ary[j].s = -1;
                i --;
                break;
            }
        }
    }
}

int main(void)
{
    int L, M;
    int i, cnt = 0;
    pos *Mary;
   
    scanf("%d%d", &L, &M);
   
    Mary = (pos *)malloc(sizeof(pos)*M);
   
    for (i = 0; i < M; i ++)
    {
        scanf("%d%d", &Mary[i].s, &Mary[i].e);
    }

    Join(Mary, M);
    for (i = 0; i < M; i++)
    {
        if (Mary[i].s != -1)
        {
            cnt += Mary[i].e - Mary[i].s + 1;
        }
    }
    cnt = L+1 - cnt;
    printf("%d\n", cnt);                                                                                          
    free(Mary);                                                                                                   
}
测了一下，应该没有什么问题，你再试试