問(wèn)題描述

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

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

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

輸出要求

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

輸入樣例

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