P1047 校门外的树

calendar May 5, 2026 · 4 分钟阅读 · 模拟  ·
分享到: linkedin copy

文章目录

题目信息

字段 内容
题号 P1047
难度 红题（入门）
知识点 模拟、区间标记

题目描述

校门外马路上有一排树，编号从 0 到 L。后来修路，需要移除其中一些区间的树。

给出 m 个区间 [a_i, b_i]（两端点inclusive），这些区间内的树全部被移除。求移除之后马路上还剩下多少棵树。

输入格式：

  • 第一行两个整数 L 和 m（0 ≤ L ≤ 10000，1 ≤ m ≤ 100）
  • 接下来 m 行，每行两个整数 a_i, b_i，表示要移除的区间

输出格式：一个整数，表示剩余的树的数量。

解题思路

核心思想

最直接的做法：枚举 + 区间判定。

  1. 初始化一个布尔数组 exist[0..L]，全部设为 true（表示树还在）
  2. 对每个区间 [a_i, b_i]，将该范围内的 exist[j] 全部设为 false
  3. 遍历 0..L，统计 exist[j] 为 true 的个数

有一种原始的逐点判定的方式：

for (int j = 0; j <= L; j++) {
    r = 1;                          // 默认 j 位置有树
    for (int k = 0; k < m; k++) {
        if (a[k] <= j && j <= b[k]) {  // j 被某个区间覆盖
            r = 0;
            break;
        }
    }
    s += r;                        // r=1 表示没树，r=0 表示有树
}

这里 s 累计的是未被覆盖的位置数，即剩余树的数量。

进阶优化：区间标记（差分数组）

原始做法对每个位置都要遍历全部 m 个区间，时间复杂度 O(L × m)。当 L 很大时效率不佳。

更优做法：区间标记。把每个区间 [a, b] 直接标记到数组上，只需 O(L + m)：

// exist[i] = true 表示 i 位置还有树
vector<bool> exist(L + 1, true);
for (int i = 0; i < m; i++) {
    cin >> a >> b;
    for (int j = a; j <= b; j++) {
        exist[j] = false;          // 区间内的树被移除
    }
}
int cnt = 0;
for (int i = 0; i <= L; i++) {
    if (exist[i]) cnt++;
}

两种思路本质相同，但区间标记在遍历区间时不需要重复检查每个 j 的所有区间。

完整代码

C++

#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int L, m;
    cin >> L >> m;

    // exist[i] = true 表示位置 i 还有树
    vector<bool> exist(L + 1, true);

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        for (int j = a; j <= b; j++) {
            exist[j] = false;
        }
    }

    int cnt = 0;
    for (int i = 0; i <= L; i++) {
        if (exist[i]) {
            cnt++;
        }
    }

    cout << cnt << "\n";
    return 0;
}

关键代码讲解

1. 区间标记

for (int j = a; j <= b; j++) {
    exist[j] = false;
}

这里注意是 <= b 而不是 < b，因为区间是闭区间 [a, b]，两端都算在内。这也是本题最常见的错误之一。

2. 统计答案

int cnt = 0;
for (int i = 0; i <= L; i++) {
    if (exist[i]) cnt++;
}

L ≤ 10000，遍历一次数组完全没问题。如果 L 更大，可以用差分数组来进一步优化，但本题规模不需要。

复杂度分析

方法 时间复杂度 空间复杂度
区间标记 O(L × m)（最坏情况） O(L)
逐点判定（原始代码） O(L × m) O(1) 额外

本题 L ≤ 10000，m ≤ 100，最多操作 1000100 次，完全在限制内。

易错点

  1. 区间是闭区间：判断条件是 a <= j && j <= b，不是 a < j && j < b，漏掉等号会导致边界树算错
  2. 遍历上界是 <= L：树的位置编号从 0 到 L，要用 <= 而不是 <
  3. 数组大小：布尔数组大小为 L + 1，避免越界

其他语言解法

Python

"""P1047 校门外的树 - Python 实现"""
from typing import List


def solve() -> None:
    """读取道路长度 L 和区间数 m，统计移除后剩余的树的数量"""
    L, m = map(int, input().split())

    exist: List[bool] = [True] * (L + 1)

    for _ in range(m):
        a, b = map(int, input().split())
        for j in range(a, b + 1):
            exist[j] = False

    cnt = sum(1 for x in exist if x)
    print(cnt)


if __name__ == '__main__':
    solve()

Java

import java.io.BufferedInputStream;
import java.io.IOException;
import java.io.PrintWriter;

/**
 * P1047 校门外的树
 * 洛谷强制要求类名为 Main，禁止使用 Scanner（会 MLE）
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedInputStream bis = new BufferedInputStream(System.in);
        PrintWriter pw = new PrintWriter(System.out);

        int L = readInt(bis);
        int m = readInt(bis);

        boolean[] exist = new boolean[L + 1];
        for (int i = 0; i <= L; i++) {
            exist[i] = true;
        }

        for (int i = 0; i < m; i++) {
            int a = readInt(bis);
            int b = readInt(bis);
            for (int j = a; j <= b; j++) {
                exist[j] = false;
            }
        }

        int cnt = 0;
        for (boolean b : exist) {
            if (b) cnt++;
        }

        pw.println(cnt);
        pw.flush();
    }

    private static int readInt(BufferedInputStream bis) throws IOException {
        int result = 0;
        int c;
        do {
            c = bis.read();
        } while (c != -1 && c <= ' ');
        while (c >= '0' && c <= '9') {
            result = result * 10 + (c - '0');
            c = bis.read();
        }
        return result;
    }
}

Go

package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	in := bufio.NewReader(os.Stdin)

	var L, m int
	fmt.Fscan(in, &L, &m)

	exist := make([]bool, L+1)
	for i := 0; i <= L; i++ {
		exist[i] = true
	}

	for i := 0; i < m; i++ {
		var a, b int
		fmt.Fscan(in, &a, &b)
		for j := a; j <= b; j++ {
			exist[j] = false
		}
	}

	cnt := 0
	for _, v := range exist {
		if v {
			cnt++
		}
	}

	fmt.Println(cnt)
}

JavaScript

'use strict';

/**
 * P1047 校门外的树
 * @param {string} input - 标准输入字符串
 * @returns {number} 剩余树的数量
 */
function countTrees(input) {
    const tokens = input.trim().split(/\s+/).map(Number);
    const L = tokens[0];
    const m = tokens[1];
    const exist = new Array(L + 1).fill(true);

    let idx = 2;
    for (let i = 0; i < m; i++) {
        const a = tokens[idx++];
        const b = tokens[idx++];
        for (let j = a; j <= b; j++) {
            exist[j] = false;
        }
    }

    return exist.filter(Boolean).length;
}

function main() {
    const input = require('fs').readFileSync('/dev/stdin', 'utf8');
    console.log(countTrees(input));
}

main();