校门外的树1110

太过爱你忘了你带给我的痛 2021-11-02 01:54 249阅读 0赞

#### 题目描述: ####

> 某校大门外长度为 L 的马路上有一排树，每两棵相邻的树之间的间隔都是 1 米。我们可以把马路看成一个数轴，马路的一端在数轴 0 的位置，另一端在 L 的位置；数轴上的每个整数点，即 0, 1, 2, ..., L，都种有一棵树。由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。

#### 输入描述： ####

> 输入两个整数 L (1 <= L <= 100000) 和 M (1 <= M <= 100)，L 代表马路的长度，M 代表区域的数目，L 和 M 之间用一个空格隔开。接下来的 M 行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。

#### 输出描述： ####

> 占一行，马路上剩余的树的数目

#### 样例输入: ####

> 500 3
> 
> 150 300
> 
> 100 200
> 
> 470 471

#### 样例输出: ####

> 298

思想：将树的存在与否设置为标志数，1表示存在，0表示被移走，最后只统计1的个数即为数留下的个数

一开始想的很麻烦：

1 #include<iostream>
     2 using namespace std;
     3 int main(){
     4     int road,area,i,j,n;
     5     while(cin>>road>>area){
     6         int m[area][2];
     7         int sum=0,all=0;
     8         for(i=0;i<area;i++){
     9             cin>>m[i][0]>>m[i][1];
    10         }
    11         for(i=0;i<area-1;i++){
    12             for(j=i+1;j<area;j++){
    13                 if(m[i][0]>m[j][1]){
    14                     continue;
    15                 }
    16                 else if(m[i][0]==m[j][1]){
    17                     sum=sum+1;
    18                 }
    19                 else{
    20                     if(m[i][0]>=m[j][0]){
    21                         if(m[i][1]<m[j][1]){
    22                             sum=sum+m[i][1]-m[i][0]+1;
    23                         }
    24                         else{
    25                             sum=sum+m[j][1]-m[i][0]+1;
    26                         }
    27                     }
    28                     else{
    29                         if(m[i][1]<m[j][0]){
    30                             continue;
    31                         }
    32                         else if(m[i][1]>=m[j][0]&&m[i][1]<=m[j][1]){
    33                             sum=sum+m[i][1]-m[j][0]+1;
    34                         }
    35                         else{
    36                             sum=sum+m[j][1]-m[j][0]+1;
    37                         }
    38                     }
    39                 }
    40             }
    41         }
    42         for(i=0;i<area;i++){
    43             all=all+m[i][1]-m[i][0]+1;
    44         } 
    45         all=road+1-all+sum;
    46         cout<<all<<endl;
    47     }
    48     return 0;
    49 }

升级的做法;

1 #include<iostream>
     2 using namespace std;
     3 int main(){
     4     int L,M,i,j;
     5     while(cin>>L>>M){
     6         int t[L+1];
     7         int m[M][2];
     8         int sum=0;
     9         for(i=0;i<M;i++){
    10             cin>>m[i][0]>>m[i][1];
    11         }
    12         for(i=0;i<L+1;i++){
    13             t[i]=1;
    14         }
    15         for(i=0;i<M;i++){
    16             for(j=m[i][0];j<=m[i][1];j++){
    17                 t[j]=0;
    18             }
    19         }
    20         for(i=0;i<L+1;i++){
    21             if(t[i]==1){
    22                 sum++;
    23             }
    24         }
    25         cout<<sum<<endl;
    26     }
    27     return 0;
    28 }

希望有所帮助

转载于:https://www.cnblogs.com/zq-dmhy/p/10996965.html