題目描述

某校大門外長度為?ll?的馬路上有一排樹，每兩棵相鄰的樹之間的間隔都是?11?米。我們可以把馬路看成一個數軸，馬路的一端在數軸?00?的位置，另一端在?ll?的位置；數軸上的每個整數點，即?0,1,2,\dots,l0,1,2,…,l，都種有一棵樹。

由于馬路上有一些區域要用來建地鐵。這些區域用它們在數軸上的起始點和終止點表示。已知任一區域的起始點和終止點的坐標都是整數，區域之間可能有重合的部分。現在要把這些區域中的樹（包括區域端點處的兩棵樹）移走。你的任務是計算將這些樹都移走后，馬路上還有多少棵樹。

輸入格式

第一行有兩個整數，分別表示馬路的長度?ll?和區域的數目?mm。

接下來?mm?行，每行兩個整數?u, vu,v，表示一個區域的起始點和終止點的坐標。

輸出格式

輸出一行一個整數，表示將這些樹都移走后，馬路上剩余的樹木數量。

輸入輸出樣例

輸入 #1

500 3 150 300 100 200 470 471

輸出 #1

298

說明/提示

【數據范圍】

• 對于?20\%20%?的數據，保證區域之間沒有重合的部分。
• 對于?100\%100%?的數據，保證?1 \leq l \leq 10^41≤l≤104，1 \leq m \leq 1001≤m≤100，0 \leq u \leq v \leq l0≤u≤v≤l。

【題目來源】

NOIP 2005 普及組第二題

題解

首先輸入一個l表示線路長度，再輸入一個數字表示有幾段的樹要砍掉；

我們只要定義一個較大的數組，并且賦初值（比如0），就可以表示出題目所需要的數軸了。只要數組的內容是0就代表有樹木，這樣后續就可以直接for循環判斷count++了！

有幾段要砍掉就是要循環輸入然后“砍掉”幾次的樹木，直接使用while（m--）就可以了（m就是幾段，m--就是循環m次）

然后思路就是，每次循環內將數組范圍內是0的數字換成1.

然后在程序的末尾，先定義一個計數的整形（比如int count=0），記得初始化0；在進入一個FOR循環，如果a[i]==0就計數器+1（count++）；然后在程序末尾輸出count的數字就可以了。

#include<stdio.h> int main(void){int l,m,u,v,i,count=0;scanf("%d %d",&l,&m);int a[11451]={0};while(m--){scanf("%d %d",&u,&v);for(i=u;i<=v;i++){if(a[i]==0){a[i]=1;}}}for(i=0;i<=l;i++){if(a[i]==0){count++;}}printf("%d",count); }

總結

以上是生活随笔為你收集整理的洛谷P1047 [NOIP2005 普及组] 校门外的树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。