問題描述

       某校大門外長度為 L 的馬路上有一排樹，每兩棵相鄰的樹之間的間隔都是 1 米。我們可以把馬路看成一個數軸，馬路的一端在數軸 0 的位置，另一端在 L 的位置；數軸上的每個整數點，即 0， 1， 2，……， L，都種有一棵樹。       由于馬路上有一些區域要用來建地鐵。這些區域用它們在數軸上的起始點和終止點表示。已知任一區域的起始點和終止點的坐標都是整數，區域之間可能有重合的部分?，F在要把這些區域中的樹（包括區域端點處的兩棵樹）移走。你的任務是計算將這些樹都移走后，馬路上還有多少棵樹。

輸入數據

       輸入的第一行有兩個整數 L（ 1 <= L <= 10000）和 M（ 1 <= M <= 100）， L 代表馬路的長度， M 代表區域的數目， L 和 M 之間用一個空格隔開。接下來的 M 行每行包含兩個不同的整數，用一個空格隔開，表示一個區域的起始點和終止點的坐標。

輸出要求

  輸出包括一行，這一行只包含一個整數，表示馬路上剩余的樹的數目。

輸入樣例

500 3150 300100 200470 471
輸出樣例
298
解題思路
        這個問題可以概括為輸入一個大的整數閉區間，及一些可能互相重疊的在該大區間內的小的整數閉區間。在大的整數閉區間內去除這些小的整數閉區間，問之后剩下的可能不連續的整數區間內有多少個整數。這個題目給出的范圍是大的區間在 1~10000 以內，要去除的小的區間的個數是 100 個以內。因為規模較小，所以可以考慮用空間換時間，用一個大數組來模擬這些區間，數組中的每個數表示區間上的一個數。       例如，如果輸入 L 的長度是 500，則據題意可知最初有 501 棵樹。我們就用一個 501 個元素的數組來模擬這 501 棵樹，數組的下標分別代表從 1 到 501 棵樹，數組元素的值代表這棵樹是否被一走。最初這些樹都沒有被移走，所以所有數組元素的值都用 true 來表示。每當輸入一個小區間，就將這個區間對應的樹全部移走，即將這個區間對應的數組元素下標指示的元素的值置成 false。如果有多個區間對應同一個數組元素，會導致多次將某個數組元素置成 false。不過這并不影響結果的正確性。當所有小區間輸入完成，我們可以數一下剩下的仍舊為 true 的元素的個數，就可以得到最后剩下的樹的數目。當然如果最開始輸入的區間不是 500，則我們使用的數組大小就不是 500。因為題目給出的上限是 10000，所以我們可以定義一個大小是 10001 個元素的數組，這樣對所有輸入都是夠用的。
參考程序
#include <iostream>using namespace std;int main(){	int L,i,j,n;	bool trees[10001];// 用一個布爾數組模擬樹的存在情況。	for(i=0;i<10001;i++){// 賦初值		trees[i]=true;	} 	cin>>L>>n;	for(i=0;i<n;i++){		int begin,end;		cin>>begin>>end;		for(j=begin;j<=end;j++){			// 將區間內的樹移走，即賦值為 false。			trees[j]=false;		}	}	int count=0;	 //用 count 計數，數數剩余的樹的數目。	for(i=0;i<=L;i++){		if(trees[i]){			count++;		}	}	cout<<count<<endl;	return 0;}