C语言学习笔记20260626-道路树木统计（暴力标记与区间合并）

C语言学习笔记20260626-道路树木统计暴力标记与区间合并一、学习目标通过经典的“道路树木统计”问题掌握处理“区间覆盖”类问题的两种核心算法思想。深入理解暴力标记法的直观逻辑并学习如何通过区间合并法进行算法优化体会从“逐点操作”到“整体区间处理”的思维跃迁。二、问题拆解与核心逻辑本题要求计算一条长度为 L 的道路共有 L1 棵树在经过 M 次施工清理每次清理区间 [l, r] 内的所有树木后剩余树木的数量。核心约束条件为区间覆盖施工区域可能会重叠但同一位置的树木只能被清理一次。最终统计需要求出未被任何施工区间覆盖的整数点个数。三、方法一标记数组法暴力模拟3.1 核心思路利用一个数组arr来物理模拟整条道路。初始时将所有位置标记为“有树1”。每当有一个施工区间 [l, r] 时直接通过循环将该区间内的所有位置标记为“无树0”。最后遍历整个数组统计剩余“有树”的位置。3.2 完整代码实现#define_CRT_SECURE_NO_WARNINGS#includestdio.h// 方法1标记数组法intmain(){intL,M;scanf(%d %d,L,M);// 初始化道路0~L 每个位置都有树标记为1intarr[10000]{0};for(inti0;iL;i){arr[i]1;}// 处理 M 次施工将区间内的树标记为0for(inti0;iM;i){intl,r;scanf(%d %d,l,r);for(intjl;jr;j)// 注意内层循环变量应避开外层的 i{arr[j]0;}}// 统计剩余树木intcount0;for(inti0;iL;i){if(arr[i]1)count;}printf(%d,count);return0;}3.3 方法优缺点分析优点逻辑极其直观完全符合人类“画一条路把挖掉的地方涂黑最后数白点”的直觉。代码编写简单不易出错。缺点时间复杂度为 O(L M × 区间平均长度)。如果道路长度 L 达到 10^9或者区间长度极长暴力法不仅会严重超时还会因为数组过大导致内存溢出。四、方法二区间合并法数学优化4.1 核心思想化零为整不逐个去处理道路上的每一个点而是将 M 个施工区间看作整体。如果两个区间有重叠例如 [100, 200] 和 [150, 300]它们实际上等效于合并成了一个更大的区间 [100, 300]。通过合并所有重叠区间我们可以快速计算出“被挖掉的总长度”最后用总树数减去被挖掉的树数即可。4.2 完整代码实现#define_CRT_SECURE_NO_WARNINGS#includestdio.h// 方法二区间合并法效率高// 区间结构体structRange{intl,r;}arr[105];// 冒泡排序按左端点升序arr[i] 代表完整一段区间 [l, r]l 和 r 是一对绑定的数据voidsort(intm){for(inti0;im-1;i){for(intj0;jm-1-i;j){if(arr[j].larr[j1].l){structRangetarr[j];arr[j]arr[j1];arr[j1]t;}}}}intmain(){intL,M;scanf(%d%d,L,M);// 读取 M 个施工区间for(inti0;iM;i)scanf(%d%d,arr[i].l,arr[i].r);// 1. 排序按区间左端点升序排列sort(M);// 2. 贪心合并区间intcnt0;// 记录被挖掉的树的总数intnowLarr[0].l,nowRarr[0].r;// 维护当前正在合并的区间 [nowL, nowR]for(inti1;iM;i){if(arr[i].lnowR){// 情况一区间重叠新左端点 当前右端点// 更新右端点取两者的最大值以扩展合并区间if(arr[i].rnowR)nowRarr[i].r;}else{// 情况二区间不重叠新左端点 当前右端点// 当前合并区间 [nowL, nowR] 结束累加其长度cntnowR-nowL1;// 开启新的合并区间nowLarr[i].l;nowRarr[i].r;}}// 3. 加上最后一段未累加的合并区间cntnowR-nowL1;// 4. 计算剩余树木总树数 (L1) - 被挖掉的树 (cnt)intans(L1)-cnt;printf(%d,ans);return0;}4.3 核心细节解析排序的必要性只有按左端点排序后所有可能重叠的区间才会连续排列我们才能通过一次线性遍历完成合并。重叠的判断条件arr[i].l nowR。只要新区间的起点在当前合并区间的终点左边或刚好相接就说明它们连成了一片。易错点循环结束后最后一段正在维护的区间[nowL, nowR]还没有被累加到cnt中必须在循环外手动加上。五、总结与工程实践建议标记数组法是理解“区间覆盖”问题的基石其“数组映射”的思想在数据规模较小时非常有效。但在面对大规模数据时区间合并法展示了极高的算法智慧。它不仅将时间复杂度降低到了 O(M log M)主要消耗在排序上更展示了“将离散的点操作转化为连续的区间操作”这一解决复杂问题的通用范式。在实际开发中当 L 较小如 10^5 以内时可采用标记法快速解题当 L 极大但 M 较小如 10^5时必须采用区间合并法。