問題描述

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

輸入數(shù)據(jù)

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

輸出要求

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

輸入樣例

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