ybt 1107:校门外的树(YBT 1107: trees outside the school gate)

1107:校门外的树

【题目描述】

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

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

【输入】

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

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

【输出】

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

【输入样例】

500 3
150 300
100 200
470 471

【输出样例】

298
#include<iostream>
using namespace std;
int main()
{
int L,M,i,j;
int section[10001]= {0};
int a,b,tree_sum=0,tree_ex,tree_new;
cin>>L>>M;//输入马路长度与区域数目
for (i=0; i<M; i++)
{
cin>>a>>b;//输入起始点与终止点
for(j=a; j<=b; j++) //令范围内的树移走
section[j]=1;
}
for(i=0; i<=L; i++) //统计马路长度内被移走的树的数目
if(section[i]==1)
tree_sum++;
tree_ex=L+1;//原来的树的数目
tree_new=tree_ex-tree_sum;//移走后的树的数目
cout<<tree_new<<endl;
return 0;
}
————————

1107: trees outside the school gate

[Title Description]

There is a row of trees on the road with a length of L outside the gate of a school, and the interval between each two adjacent trees is 1 meter. We can regard the road as a number axis. One end of the road is at the position of number axis 0 and the other end is at the position of L; Every integer point on the number axis, i.e. 0, 1, 2,…, l, has a tree.

Because there are some areas on the road to build subways. These areas are represented by their starting and ending points on the number axis. It is known that the coordinates of the starting point and ending point of any region are integers, and there may be overlapping parts between regions. Now remove the trees in these areas (including the two trees at the end of the area). Your task is to calculate how many trees there are on the road after all these trees are removed.

[input]

The first line has two integers L (1 ≤ L ≤ 10000) and m (1 ≤ m ≤ 100). L represents the length of the road, M represents the number of areas, and l and m are separated by a space. The next M lines contain two different integers, separated by a space, representing the coordinates of the starting and ending points of an area.

For 20% of the data, there is no overlap between regions; For other data, there is overlap between regions.

[output]

Includes a row that contains only an integer indicating the number of trees remaining on the road.

[input example]

500 3
150 300
100 200
470 471

[output example]

298
#include<iostream>
using namespace std;
int main()
{
int L,M,i,j;
int section[10001]= {0};
int a,b,tree_sum=0,tree_ex,tree_new;
cin>>L>>M;//输入马路长度与区域数目
for (i=0; i<M; i++)
{
cin>>a>>b;//输入起始点与终止点
for(j=a; j<=b; j++) //令范围内的树移走
section[j]=1;
}
for(i=0; i<=L; i++) //统计马路长度内被移走的树的数目
if(section[i]==1)
tree_sum++;
tree_ex=L+1;//原来的树的数目
tree_new=tree_ex-tree_sum;//移走后的树的数目
cout<<tree_new<<endl;
return 0;
}