# P1047 [NOIP 2005 普及组] 校门外的树 ## 题目描述 某校大门外长度为 $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$。 **【题目来源】** NOIP 2005 普及组第二题 c++,不写注释

<think>题目要求计算在移走若干区间内的树之后，马路上剩余的树木数量。马路从0到l（包括0和l）每个整数点都有一棵树。 输入：第一行是l和m（m个区间），接下来m行，每行是一个区间的起点u和终点v（包括端点）。 输出：剩余树木的数量。 注意：区间可能重叠。 思路： 1. 初始的树木数量是 l+1（因为包括0到l，共l+1棵树）。 2. 我们需要计算所有区间覆盖的总长度（注意重叠部分不能重复计算）。 3. 剩余树木数量 = 总树木数 - 被移走的树木数量（即被覆盖的点的数量）。 但是，直接计算覆盖的总长度需要合并区间。因为区间可能重叠，所以我们可以先合并区间，然后计算每个合并后的区间的长度（即移走的树木数量），最后用总树木数减去移走的总数。 步骤： a. 读取l和m。 b. 读取m个区间，并将每个区间存储为列表。 c. 按照区间的起点进行排序。 d. 合并区间：遍历排序后的区间，如果当前区间与上一个合并后的区间有重叠，则合并；否则，将上一个合并后的区间加入结果，并更新当前区间为新的区间。 e. 计算每个合并后的区间的长度（注意：区间包括端点，所以长度是（终点-起点+1））。 f. 总覆盖的树木数量 = 所有合并后的区间长度之和。 g. 剩余树木 = (l+1) - 总覆盖的树木数量。 示例：输入为 l=500, m=3, 区间为 [150,300], [100,200], [470,471] 合并区间：先排序-> [100,200], [150,300], [470,471] -> 合并后得到 [100,300] 和 [470,471] 第一个区间长度：300-100+1=201 第二个区间长度：471-470+1=2 总覆盖树木=201+2=203 剩余树木=501-203=298 代码实现：</think>### 题目解析 该问题要求计算在移除多个可能重叠的区间内树木后，马路上剩余的树木数量。关键点在于处理区间重叠，避免重复计算移除的树木。解决思路如下： 1. **初始化**：马路上共有 \( l + 1 \) 棵树（从位置 \( 0 \) 到 \( l \)）。 2. **区间合并**：将重叠的区间合并为连续的大区间，避免重复计数。 3. **计算移除数量**：对每个合并后的区间计算移除树木数（区间长度 = \( \text{终点} - \text{起点} + 1 \)）。 4. **计算结果**：剩余树木数 = 总树木数 - 所有合并区间移除的树木总数。 ### 代码实现（Python） ```python def main(): l, m = map(int, input().split()) intervals = [] for _ in range(m): u, v = map(int, input().split()) intervals.append((u, v)) # 按起点排序 intervals.sort(key=lambda x: x[0]) # 合并重叠区间 merged = [] start, end = intervals[0] for i in range(1, m): if intervals[i][0] <= end + 1: # 重叠或相邻（注意树木是离散点） end = max(end, intervals[i][1]) else: merged.append((start, end)) start, end = intervals[i] merged.append((start, end)) # 加入最后一个区间 # 计算移除的树木总数 removed = 0 for s, e in merged: removed += (e - s + 1) # 输出剩余树木 print(l + 1 - removed) if __name__ == "__main__": main() ``` ### 代码说明 1. **输入处理**：读取马路长度 \( l \) 和区间数量 \( m \)，并存储所有区间。 2. **区间排序**：按起点升序排序，便于合并。 3. **区间合并**： - 遍历排序后的区间，若当前区间与上一区间重叠（或相邻），则合并为更大的区间。 - 否则将上一合并区间加入结果，并开始新区间合并。 4. **计算移除量**：对每个合并区间计算移除树木数（端点差+1）。 5. **输出结果**：剩余树木数 = 总树数 \( (l + 1) \) - 移除总数。 ### 示例验证 输入： ``` 500 3 150 300 100 200 470 471 ``` - 合并后区间：`[100, 300]` 和 `[470, 471]` - 移除树木：\( (300-100+1) + (471-470+1) = 201 + 2 = 203 \) - 剩余树木：\( 501 - 203 = 298 \) 输出：`298`，符合题目要求。