• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

(题号丢失)校门外的树

开发技术 开发技术 6天前 7次浏览

描述

某校大门外长度为L的马路上有一排树,每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴,马路的一端在数轴0的位置,另一端在L的位置;数轴上的每个整数点,即0,1,2,……,L,都种有一棵树。

由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数,区域之间可能有重合的部分。现在要把这些区域中的树(包括区域端点处的两棵树)移走。你的任务是计算将这些树都移走后,马路上还有多少棵树。

 

输入

第一行有两个整数L(1 ≤ L ≤ 10000)和M(1 ≤ M ≤ 100),L代表马路的长度,M代表区域的数目,L和M之间用一个空格隔开。接下来的M行每行包含两个不同的整数,用一个空格隔开,表示一个区域的起始点和终止点的坐标。

对于20%的数据,区域之间没有重合的部分;对于其它的数据,区域之间有重合的情况。

 

输出

包括一行,这一行只包含一个整数,表示马路上剩余的树的数目。

 

输入样例 1 

500 3
150 300
100 200
470 471

输出样例 1

298


这一题我最初是把它考虑成了一个布尔型的一维数组,先初始化把所有的元素都赋值为真,然后输入。
把输入的两个数之间的元素改为假,如果已经为假,则不作修改,最后循环统计为真的元素数量。
代码:
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int main()
 4 {
 5     int l,n,a,b,maxx,minn,s=0;
 6     cin>>l>>n;
 7     bool k[l+1];
 8     for(int i=0;i<=l;i++) k[i]=1;
 9     for(int i=1;i<=n;i++)
10     {
11         cin>>a>>b;
12         for(int j=a;j<=b;j++)
13         {
14             if(k[j]==1) k[j]=0;
15         }
16     }
17     for(int i=0;i<=l;i++)
18     {
19         if(k[i]==1) s++;
20     }
21     cout<<s;
22     return 0;
23 }

OK!解决问题!

 

喜欢 (0)