题目内容
内容
某校大门外长度为 l 的马路上有一排树,每两棵相邻的树之间的间隔都是 11 米。我们可以把马路看成一个数轴,马路的一端在数轴 0 的位置,另一端在 l 的位置;数轴上的每个整数点,即 0,1,2,…,l,都种有一棵树。
由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数,区域之间可能有重合的部分。现在要把这些区域中的树(包括区域端点处的两棵树)移走。你的任务是计算将这些树都移走后,马路上还有多少棵树。
输入
第一行有两个整数,分别表示马路的长度 l 和区域的数目 m。
接下来 m 行,每行两个整数 u,v,表示一个区域的起始点和终止点的坐标。
输出
输出一行一个整数,表示将这些树都移走后,马路上剩余的树木数量。
样例
输入 | 输出 |
---|---|
500 3 | |
150 300 | |
100 200 | |
470 471 | 298 |
数据范围
• 对于 20%20% 的数据,保证区域之间没有重合的部分。
• 对于 100%100% 的数据,保证 1≤l≤104,1≤m≤100,0≤u≤v≤l。
解题思路
本体的解题思路,是可以将每个位置的树的状态,用数组存储起来,定义一个数组,进行初始化一个随机值(比如1),将施工路段的位置进行读入,改变里面的树的状态(1改为0),就是改变初始值为另一个值,这个值是几都无所谓,多次读入施工路段的位置,进行改变树的状态,最后只需读出未改变的树的状态有多少(计算数组中状态为1的树木有多少个),就可以算出剩余树木
运行代码
#include<stdio.h>
int main()
{
int sum = 0;
int x, y;
int i, j;
int l, m;
int art[10000] = {
0 };//建立一个数组用来存放每个树的状态
scanf("%d %d", &l, &m);//输入路长和施工路段个数
for (i = 0; i < m;i++)
{
scanf("%d %d", &x, &y); //输入多组施工路段的起点终点
//字符串的写入不用加&,整数字符的写入需要&取地址符
for (j = x;j <= y;j++)
{
art[j] = 1; //将施工路段移除的树木打上标记
}
}
for (i = 0; i <= l;i++) //注意一条路的两端也要栽树,两端都要取
{
if (art[i] != 1) //统计未移除的树木(为打上标记的)
sum++;
}
printf("%d", sum);//看清题目要求的是剩余数目
return 0;
}