【題目描述】
某校大門外長度為L的馬路上有一排樹，每兩棵相鄰的樹之間的間隔都是1米。我們可以把馬路看成一個數(shù)軸，馬路的一端在數(shù)軸0的位置，另一端在L的位置；數(shù)軸上的每個整數(shù)點，即0，1，2，……，L，都種有一棵樹。
由于馬路上有一些區(qū)域要用來建地鐵。這些區(qū)域用它們在數(shù)軸上的起始點和終止點表示。已知任一區(qū)域的起始點和終止點的坐標(biāo)都是整數(shù)，區(qū)域之間可能有重合的部分?，F(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ù)目。
對于20%的數(shù)據(jù)，區(qū)域之間沒有重合的部分；
對于其它的數(shù)據(jù)，區(qū)域之間有重合的情況。
【輸入樣例】
500 3
150 300
100 200
470 471
【輸出樣例】
298
【問題解析】
分析數(shù)據(jù)
輸入共M+1行
第一行 兩個整數(shù)L和M（L代表馬路的長度，M代表區(qū)域的數(shù)目）
1 <= L <= 10000， 1 <= M <= 100
接下來的M行每行包含兩個不同的整數(shù)，用一個空格隔開，表示一個區(qū)域的起始點和終止點的坐標(biāo)。
規(guī)則條件
區(qū)域是閉區(qū)間，里面的樹都要移除，區(qū)間可能會有重合。
要點：所給的區(qū)域起始點和終止點坐標(biāo)并未說明誰大誰小，比如30 50和50 30等價，但是在寫程序時要做這個判斷。
輸出結(jié)果
一個整數(shù)，剩余樹的棵數(shù)。
題目意思：長為L的馬路上，在0~L上每隔一米就有一棵樹，所以一共有L+1棵。由于要修地鐵，要把指定區(qū)域的樹移除，比如給出30 50，就表明第30米到50米的樹都移除?，F(xiàn)在給出馬路長度L、要移除樹的區(qū)域個數(shù)M以及M個區(qū)間，求剩下多少棵樹。
這里有一個點要特別注意，題目所給的區(qū)域起始點和終止點坐標(biāo)并未說明誰大誰小，比如30 50和50 30等價，但是在寫程序時要做這個判斷。
【解題思路與步驟】
讀入數(shù)據(jù)：
int L,M,flag=0,t; //L為路長，M為區(qū)域數(shù)，flag用來統(tǒng)計剩余的數(shù)。
scanf("%d%d",&L,&M);
int a[10001];
for(int i=0;i<=L;i++)
a[i]=1;
將M個區(qū)域內(nèi)的樹都移除
int p,q;//倆坐標(biāo)軸
for(int i=0;i<M;i++)
{
scanf("%d%d",&p,&q);
if(p>q)
{
t=p;
p=q;
q=t;
}
for(int j=p;j<=q;j++)
{
a[j]=0;
}
}
要點：
1. 外層for循環(huán)是遍歷M個區(qū)域。
2. 讀入?yún)^(qū)域起始點坐標(biāo)和終點坐標(biāo)時要判斷大小，要保證起始點坐標(biāo)不大于終點坐標(biāo)。
3. 內(nèi)層的for循環(huán)用來將樹移除。
統(tǒng)計剩余樹
for(int i=0;i<=L;i++)
{
if(a[i]==1)// 表示該地方樹還在
flag++;
}
要點：
數(shù)組a中元素，其中仍為1的表示該地方樹還在，進(jìn)行統(tǒng)計。
輸出
printf("%d",flag);
要點：
flag的初值為0。
題目大意與要求分析完了，來看看如何解題：
第一步：讀入數(shù)據(jù)。首先讀入兩個整數(shù)L，M。再用一個數(shù)組，里面的前L個元素初值置為1，表示有L棵樹。
int L,M,flag=0,t;
scanf("%d%d",&L,&M);
int a[10001];
for(int i=0;i<=L;i++)
a[i]=1;
第二步：將M個區(qū)域內(nèi)的樹都移除。這是最為重要的一步，首先使用for循環(huán)遍歷每個區(qū)域，接著移除每個區(qū)域內(nèi)的樹；要移除每個區(qū)域內(nèi)的樹，先用兩個整型變量p,q讀取區(qū)域的起始點坐標(biāo)和終點坐標(biāo)，如果起始點坐標(biāo)大于終點坐標(biāo)，則兩個數(shù)交換。再將表示樹的數(shù)組a中下標(biāo)p到q的元素置為0，表示樹已經(jīng)移除。此時該區(qū)域的樹已經(jīng)移除完畢，進(jìn)行下一個區(qū)域的操作，直到循環(huán)結(jié)束。
int p,q;
for(int i=0;i<M;i++)
{
scanf("%d%d",&p,&q);
if(p>q)
{
t=p;
p=q;
q=t;
}
for(int j=p;j<=q;j++)
{
a[j]=0;
}
}
第三步：統(tǒng)計還剩余多少樹。用for循環(huán)遍歷數(shù)組a前L個元素，其中仍為1的表示該地方樹還在，進(jìn)行統(tǒng)計。
for(int i=0;i<=L;i++)
{
if(a[i]==1)
flag++;
}
第四步：輸出。輸出剩余樹的棵數(shù)。
printf("%d",flag);
【實現(xiàn)代碼 】
#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
int L,M,flag=0,t;
scanf("%d%d",&L,&M);
int a[10001];
for(int i=0;i<=L;i++)
a[i]=1;
int p,q;
for(int i=0;i<M;i++)
{
scanf("%d%d",&p,&q);
if(p>q)
{
t=p;
p=q;
q=t;
}
for(int j=p;j<=q;j++)
{
a[j]=0;
}
}
for(int i=0;i<=L;i++)
{
if(a[i]==1)
flag++;
}
printf("%d",flag);
return 0;
}
聯(lián)系客服
