管闲事的小明-nyoj51

描述某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0，1，2，……，L，都种有一棵树。　　由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。　　已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。聪明的小明干了一件又一件事，他觉得这个很有意思，就想用计算机来帮助建筑工人统计这些树，现在任务来了，计算将这些树都移走后，马路上还有多少棵树。

输入

第一行是一个整数N表示有N组测试数据（1<=N<=100) 每组测试数据的第一行有两个整数：L（1 <= L <= 10000）和 M（1 <= M <= 100），L代表马路的长度，M代表区域的数目，L和M之间用一个空格隔开。接下来的M行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。

输出

输出包括一行，这一行只包含一个整数，表示马路上剩余的树的数目。

样例输入

样例输出

#if 0
//总是wa。我的思路是：把区域一个个处理，若遇到相连或重叠的区域，改变尾端，否则，首段尾端一起变。 我想可能是思路太复杂，有特殊情况没考虑
#include <stdio.h>
#include <stdlib.h>
struct se
{
    int s;
    int e;
}area[101];

int cmp(const void *x, const void *y)
{
    struct se *m = (struct se *)x;
    struct se *n = (struct se *)y;
    return m->s - n->s;
}

int main()
{
    int n, i, len, m, sum, a, b, flag;
    scanf("%d", &n);
    while(n--){

            scanf("%d %d", &len, &m);
            len++;/*加上开头端点*/
            for(i = 1; i <= m; i++){

                    scanf("%d %d", &area[i].s, &area[i].e);

            }
            qsort(area+1, m, sizeof(area[0]), cmp);
            a = area[1].s;/*记录区域首端*/
            b = area[1].e;/*记录区域尾端*/
            sum = 0;        
            flag = 1;
            for(i = 1; i < m; i++){

                    if(area[i+1].s <= b && area[i+1].e >= b)
                    {
                        b = area[i+1].e;
                        flag = 1;
                    }
                    else if(area[i+1].s > b)
                    {
                        flag = 0;
                        sum += b-a+1;
                        a = area[i+1].s;
                        b = area[i+1].e;
                        sum += b-a+1;
                    }
                //    if(flag == 0)
                //    {
                //        sum += b-a+1;
                //    }

            }
            if(flag == 1)
            {
                sum += b-a+1;
            }
            printf("%d
", len-sum);
            
    }
    return 0;
}
#endif
//AC了，思路比上一个简单，每组数据测试前，清零，然后在每个区域内都赋值1，最后在从头往后（下标为0到M-1）统计值为1的数组元素，最最后用总数去剪它即可
#include <stdio.h>
#include <string.h>
#define M 10002
int tray[M];

int main()
{
    int n, len, num, a, b, sum, i;
    scanf("%d", &n);
    while(n--){

            memset(tray, 0, sizeof(tray));
            sum = 0;
            scanf("%d %d", &len, &num);
            while(num--){

                    scanf("%d %d", &a, &b);
                    for(i = a; i <= b; i++)
                    {
                        tray[i] = 1;
                    }
                    
            }
            for(i = 0; i < M; i++){

                    if(tray[i] = 1)
                        sum++;

            }
            printf("%d
", len+1-sum);

    }
    return 0;
}

View Code