問題描述
某校大門外長度為 L 的馬路上有一排樹,每兩棵相鄰的樹之間的間隔都是 1 米。我們可以把馬路看成一個數(shù)軸,馬路的一端在數(shù)軸 0 的位置,另一端在 L 的位置;數(shù)軸上的每個整數(shù)點,即 0,1,2,......,L,都種有一棵樹潜腻。由于馬路上有一些區(qū)域要用來建地鐵埃儿。 這些區(qū)域用它們在數(shù)軸上的起始點和終止點表示。 已知任一區(qū)域的起始點和終止點的坐標(biāo)都是整數(shù), 區(qū)域之間可能有重合的部分融涣。 現(xiàn)在要把這些區(qū)域中的樹(包括區(qū)域端點處的兩棵樹)移走童番。你的任務(wù)是計算將這些樹都移走后,馬路上還有多少棵樹。
輸入
輸入的第一行有兩個整數(shù) L(1 <= L <= 10000)和 M(1 <= M <= 100),L 代表馬路的長度,M 代表區(qū)域的數(shù)目,L 和 M 之間用一個空格隔開威鹿。接下來的 M 行每行包含兩個不同的整數(shù),用一個空格隔開,表示一個區(qū)域的起始點和終止點的坐標(biāo)剃斧。
輸出
輸出包括一行,這一行只包含一個整數(shù),表示馬路上剩余的樹的數(shù)目。
輸入樣列
500 3
150 300
100 200
470 471
輸出樣例
297
算法實現(xiàn)
using System;
namespace Questions{
class Program{
static void Main(string[] args){
//輸入L M
string input = Console.ReadLine();
//格式轉(zhuǎn)換
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){
//循環(huán)M次獲取M行數(shù)據(jù)
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行的數(shù)據(jù)忽你，第一個比第二個大這交換位置
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("輸入錯誤幼东！");
}
}
//遍歷區(qū)域之間重合的部分
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;
}
}
}
//計算移走的樹的數(shù)目
int sum = 0;
for (int i = 0; i < M; i++)
{
//當(dāng)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();
}
}
}