0005-校门外的树

问题描述

某校大门外长度为 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

输出样例

297

算法实现

using System;

namespace Questions{
    class Program{
        static void Main(string[] args){
            //输入L M
            string input = Console.ReadLine();
            //格式转换
            string[] str = input.Split(' ');
            int L = int.Parse(str[0]);
            int M = int.Parse(str[1]);
            int[] num = new int[M * 2];
            if (L >= 1 && L <= 10000 && M >= 1 && M <= 100){
                //循环M次获取M行数据
                for (int i = 0; i < M; i++){
                    input = Console.ReadLine();
                    str = input.Split(' ');
                    num[2 * i] = int.Parse(str[0]);
                    num[2 * i + 1] = int.Parse(str[1]);
                    //如果输入i行的数据，第一个比第二个大这交换位置
                    if (num[2 * i] > num[2 * i + 1])
                        num[2 * i] = num[2 * i + 1] + (num[2 * i + 1] = num[2 * i]) * 0;
                    else if (num[2 * i] == num[2 * i + 1]){
                        Console.WriteLine("输入错误！");
                    }
                }

                //遍历区域之间重合的部分
                for (int i = 0; i < M; i++){
                    for (int j = 0; j < i; j++){
                        if (num[2 * i + 1] <= num[2 * j + 1] && num[2 * i] >= num[2 * j]){
                            //[num[2 * i],num[2 * i+1]]被[num[2 * j],num[2 * j+1]]包含时
                            num[2 * i] = 0;
                            num[2 * i + 1] = 0;
                        }
                        else if (num[2 * i + 1] >= num[2 * j + 1] && num[2 * i] <= num[2 * j]){
                            //[num[2 * i],num[2 * i+1]]包含[num[2 * j],num[2 * j+1]]
                            num[2 * j] = 0;
                            num[2 * j + 1] = 0;
                        }
                        else if (num[2 * i + 1] <= num[2 * j + 1] && num[2 * i + 1] >= num[2 * j] && num[2 * i] < num[2 * j]){
                            //num[2 * i+1]在[num[2 * j],num[2 * j+1]]之间num[2 * i]小于num[2 * j]
                            num[2 * i + 1] = num[2 * j] - 1;
                        }
                        else if (num[2 * i] <= num[2 * j + 1] && num[2 * i] >= num[2 * j] && num[2 * i + 1] > num[2 * j + 1]){
                            //num[2 * i]在[num[2 * j],num[2 * j+1]]之间num[2 * i+1]大于num[2 * j+1]
                            num[2 * i] = num[2 * j + 1] + 1;
                        }
                    }
                }

                //计算移走的树的数目
                int sum = 0;
                for (int i = 0; i < M; i++)
                {
                    //当num[2 * i + 1] !=num[2 * i]时，该段有树需要被 移走
                    if (num[2 * i + 1] !=num[2 * i])
                        sum += num[2 * i + 1] - num[2 * i] + 1;
                }
                sum = L - sum;
                Console.WriteLine(sum);
            }
            Console.ReadKey();
        }
    }
}