校门外的树

[校门外的树]([P1047 NOIP2005 普及组] 校门外的树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn))

[NOIP2005 普及组] 校门外的树

题目描述

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

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

输入格式

第一行有两个整数，分别表示马路的长度 $l$ 和区域的数目 $m$。

接下来 $m$ 行，每行两个整数 $u, v$，表示一个区域的起始点和终止点的坐标。

输出格式

输出一行一个整数，表示将这些树都移走后，马路上剩余的树木数量。

样例 #1

样例输入 #1

500 3
150 300
100 200
470 471

样例输出 #1

298

提示

【数据范围】

• 对于 $20%$ 的数据，保证区域之间没有重合的部分。
• 对于 $100%$ 的数据，保证 $1 \leq l \leq 10^4$，$1 \leq m \leq 100$，$0 \leq u \leq v \leq l$。

1. 代码

   #include <iostream>
   #include <algorithm>
   
   
   using namespace std;
   
   
   struct Range {
       int begin;
       int end;
   };
   
   bool com(Range a, Range b) {
       if (a.begin == b.begin) {
           return a.end > b.end;//如果相等，就按照end反向排序
       }
       return a.begin < b.begin;
   }
   
   int main() {
       int sum, n;
       cin >> sum >> n;
       Range ranges[n];//存放范围
       for (int i = 0; i < n; ++i) {
           cin >> ranges[i].begin >> ranges[i].end;
       }
       sort(ranges, ranges + n, com);
       sum += 1;
       int maxEnd = -1;//第一次一定会运行到最后
       for (int i = 0; i < n; ++i) {
           if (ranges[i].end <= maxEnd) {//整个范围都被减掉
               continue;
           }
           if (i > 0 && maxEnd >= ranges[i].begin) {//前面部分被剪掉
               sum -= ( ranges[i].end-maxEnd);
           } else {//dou'zai'wa'ni
               sum -= (ranges[i].end - ranges[i].begin + 1);
           }
           maxEnd=ranges[i].end;
       }
       cout << sum;
       return 0;
   }

2. 提示

   • 抽象成数组
   • 记得sum+=1,因为0处也有树
   • 通过排序算法，更好的固定范围

3. 理解

   • 将所有的树抽象成为了数周上面的点，然后我们通过范围，判断sum的减数
   • 本题有三个特殊的情况
     • 某一次的范围都在已经减了的范围，由于排了序，我们只需要判断后面的范围
     • 前面部分已经被减，我们就需要记录的maxEnd来确定范围
     • 完全没有被减过

4. 问题

   -