问题描述
某校大门外长度为 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();
}
}
}