[NOIP2005]校门外的树

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

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

思路：

  • 先基于暴力思想，定义一个长度为L的数组让每棵树0- L 的值都为0
  • 读取区域，只要覆盖到的范围就把对应位置改成1（也就是非0）
  • 在遍历一遍0的剩余数量，也就是树剩下的数量
  • 我们可以发现 其实只需要找0 有几个 就行了，覆盖到的范围的数++（也就是非0，甚至实现了记录重复了多少次）
  • 也就是求一个区间有多少个0 区间-》端点 用差分
  • 我只需要给区域左端点+1 右端点的下一位-1 即可遍历读取所有点的数值（差分的思想 a[i]=s[i]+a[i-1]）
  • 读到0 cout++
    
 #include<bits/stdc++.h>
using namespace std;
//  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 L
//  区域建地铁 包括端点
//  0 0 0 0 1 1 1 1 1 1 0 0 0 0   cha[i]+a[i-1]= a[i]
//                   0
int main() {
    int L, M, sum = 0;
    int cha[10010] = { 0 };
    cin >> L;
    cin >> M;
    while (M--) {
        int a, b;
        scanf("%d %d", &a, &b);
        if (a > b)swap(a, b);
        cha[a]++;
       cha[b+1]--;
    }
    int a = 0;
    for (int i = 0; i <= L;i++) {
        a = a + cha[i];
        if (a == 0)sum++; 
      //cout << a[i] << " ";
    }
    cout << sum;
}