描述
有一个长度为整数L(1<=L<=10000)的马路,可以想象成数轴上长度为L的一个线段,起点是坐标原点,在每个整数坐标点有一棵树,即在0,1,2,...,L共L+1个位置上有L+1棵树。
现在要移走一些树,移走的树的区间用一对数字表示,如 100 200表示移走从100到200之间(包括端点)所有的树。
可能有M(1<=M<=100)个区间,区间之间可能有重叠。现在要求移走所有区间的树之后剩下的树的个数。
输入
两个整数L(1<=L<=10000)和M(1<=M<=100)。 接下来有M组整数,每组有一对数字。
输出
可能有多组输入数据,对于每组输入数据,输出一个数,表示移走所有区间的树之后剩下的树的个数。
样例输入1
4 2
1 2
0 2
11 2
1 5
4 7
0 0
样例输出1
2
5
#include <stdio.h> //数组合并 int main() { int l,n; while (scanf("%d%d",&l,&n)&&l&&n) { int i,j; int left[100]={0},right[100]={0},start,flag=1,end; for (i=0;i<n;i++) scanf("%d%d",&left[i],&right[i]); for (i=0;i<n-1;i++) //对区间从小到大排序 { for (j=i+1;j<n;j++) { if (left[i]>left[j]) { int tem=left[i]; left[i]=left[j]; left[j]=tem; tem=right[i]; right[i]=right[j]; right[j]=tem; } else if (left[i]==left[j]&&right[i]>right[j]) { int tem=right[i]; right[i]=right[j]; right[j]=tem; } } } start=left[0]; end=right[0]; for (i=0;i<n;i++) { if (i==n-1||end<left[i+1]) //处理重叠区间后 { l-=end-start+1; start=left[i+1]; } if (right[i+1]>end) end=right[i+1]; } printf("%d\n",l+1); } return 0; }
0.0分
1 人评分
C语言程序设计教程(第三版)课后习题6.4 (C语言代码)浏览:738 |
ASCII帮了大忙浏览:749 |
C语言程序设计教程(第三版)课后习题6.10 (C语言代码)浏览:749 |
输出正反三角形 (C语言代码)浏览:786 |
A+B for Input-Output Practice (IV) (C语言代码)浏览:451 |
Cylinder (C语言描述,蓝桥杯)浏览:1247 |
文科生的悲哀 (C语言代码)浏览:1400 |
P1000 (C语言代码)浏览:871 |
Hello, world! (C语言代码)浏览:714 |
矩阵乘方 (C语言代码)浏览:1023 |