校门外的树

GitHub跳转原题关系图返回列表

用布尔数组标记所有被区间覆盖的位置，再统计未移走的树。

OJ: noi_openjudge

题目 ID: ch0106-06

难度:普及-

标签:数组模拟区间python

日期: 2026-07-30 23:01

目录

  1. 题意
  2. 思路
  3. 代码
  4. Python代码
  5. C++代码
    1. 复杂度
    2. 总结

题意

数轴 00 到 LL 的每个整数位置都有树。多个闭区间内的树被移走，求剩余树数。

思路

布尔数组 removed[position] 表示该位置的树是否被移走。对每个闭区间 left 到 right 标记为真，重叠区间重复标记不会影响结果，最后统计为假的位置。

代码

Python代码

python
road_length, interval_count = map(int, input().split())
removed = [False] * (road_length + 1)

for _ in range(interval_count):
    left, right = map(int, input().split())
    for position in range(left, right + 1):
        removed[position] = True

print(removed.count(False))

C++代码

cpp
#include <cstdio>
int l,m;
int a[10005] = {0};
int main(){
    scanf("%d%d",&l,&m);
    int i,j;
    for (i=1;i<=m;i++){
        int s,t;
        scanf("%d %d",&s,&t);
        for (j=s;j<=t;j++){
            a[j] = 1;
        }
    }
    int cnt = 0;
    for (i=0;i<=l;i++){
        if(!a[i]) cnt++;
    }
    printf("%d\n",cnt);
    return 0;
}

复杂度

设所有区间长度总和为 SS，时间复杂度为 O(L+S)O(L+S)，空间复杂度为 O(L)O(L)。

总结

范围不大且只需覆盖与否时，直接标记比处理区间重叠关系更直观。