描述某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0，1，2，……，L，都种有一棵树。 由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。 已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。聪明的小明干了一件又一件事，他觉得这个很有意思，就想用计算机来帮助建筑工人统计这些树，现在任务来了，计算将这些树都移走后，马路上还有多少棵树。
- 输入
- 第一行是一个整数N表示有N组测试数据（1<=N<=100) 每组测试数据的第一行有两个整数：L（1 <= L <= 10000）和 M（1 <= M <= 100），L代表马路的长度，M代表区域的数目，L和M之间用一个空格隔开。接下来的M行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。
- 输出
- 输出包括一行，这一行只包含一个整数，表示马路上剩余的树的数目。
- 样例输入
1
500 3
150 300
100 200
470 471- 样例输出
298
#if 0
//总是wa。我的思路是：把区域一个个处理，若遇到相连或重叠的区域，改变尾端，否则，首段尾端一起变。 我想可能是思路太复杂，有特殊情况没考虑
#include <stdio.h>
#include <stdlib.h>
struct se
{
int s;
int e;
}area[]; int cmp(const void *x, const void *y)
{
struct se *m = (struct se *)x;
struct se *n = (struct se *)y;
return m->s - n->s;
} int main()
{
int n, i, len, m, sum, a, b, flag;
scanf("%d", &n);
while(n--){ scanf("%d %d", &len, &m);
len++;/*加上开头端点*/
for(i = ; i <= m; i++){ scanf("%d %d", &area[i].s, &area[i].e); }
qsort(area+, m, sizeof(area[]), cmp);
a = area[].s;/*记录区域首端*/
b = area[].e;/*记录区域尾端*/
sum = ;
flag = ;
for(i = ; i < m; i++){ if(area[i+].s <= b && area[i+].e >= b)
{
b = area[i+].e;
flag = ;
}
else if(area[i+].s > b)
{
flag = ;
sum += b-a+;
a = area[i+].s;
b = area[i+].e;
sum += b-a+;
}
// if(flag == 0)
// {
// sum += b-a+1;
// } }
if(flag == )
{
sum += b-a+;
}
printf("%d\n", len-sum); }
return ;
}
#endif
//AC了，思路比上一个简单，每组数据测试前，清零，然后在每个区域内都赋值1，最后在从头往后（下标为0到M-1）统计值为1的数组元素，最最后用总数去剪它即可
#include <stdio.h>
#include <string.h>
#define M 10002
int tray[M]; int main()
{
int n, len, num, a, b, sum, i;
scanf("%d", &n);
while(n--){ memset(tray, , sizeof(tray));
sum = ;
scanf("%d %d", &len, &num);
while(num--){ scanf("%d %d", &a, &b);
for(i = a; i <= b; i++)
{
tray[i] = ;
} }
for(i = ; i < M; i++){ if(tray[i] = )
sum++; }
printf("%d\n", len+-sum); }
return ;
}