校门外的树

题目描述

数轴 $[0, L]$ 上每个整数点 $0,1,\dots,L$ 都种有一棵树。现要移走 $M$ 个区域内的所有树（含区域端点），区域之间可能重合，求移走后剩余树的数目。输入：第一行两个整数 $L, M$ （ $1 \le L \le 10000$ ， $1 \le M \le 100$ ）；接下来 $M$ 行每行两个整数，为区域起始点和终止点坐标。输出：一行一个整数，表示剩余树的数目。样例：输入第一行为 500 3，接下来三行为 150 300、100 200、470 471；输出为 298。

思路

用布尔数组 removed 标记被移走的位置：每个区域先规范化成左小右大，再把区间内含端点的所有点置为已移走。最后统计 $[0, L]$ 中未被标记的点的个数，即为答案。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-07-07 09:53
# update_at: 2026-07-07 09:53

import sys


def merge_intervals(intervals: list[tuple[int, int]]) -> list[tuple[int, int]]:
    """按左端点排序后合并所有重叠或相接的区间。"""
    intervals.sort()
    merged: list[tuple[int, int]] = []
    for left, right in intervals:
        if merged and left <= merged[-1][1] + 1:
            merged[-1] = (merged[-1][0], max(merged[-1][1], right))
        else:
            merged.append((left, right))
    return merged


def removed_count(intervals: list[tuple[int, int]]) -> int:
    """计算合并后区间覆盖的整数点个数（含端点）。"""
    return sum(right - left + 1 for left, right in merge_intervals(intervals))


def solve() -> None:
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    it = iter(data)
    length = next(it)          # 马路长度 L
    region_count = next(it)    # 区域数 M

    intervals = [(next(it), next(it)) for _ in range(region_count)]
    # 先规范化成左小右大，再用并集长度求被移走的树。
    intervals = [(min(a, b), max(a, b)) for a, b in intervals]
    ans = (length + 1) - removed_count(intervals)
    print(ans)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 01:40
 * update_at: 2026-10-05 01:40
 */

#include <algorithm>
#include <iostream>
typedef long long ll;
using namespace std;

const int MAXL = 10005;

// removed_tree[i] = 1 表示位置 i 上的树被移走
bool removed_tree[MAXL];

int main() {
    ll L, M; // L 马路长度，M 区域数目
    cin >> L >> M;
    for (int i = 1; i <= M; i++) {
        ll a, b;
        cin >> a >> b;
        if (a > b) swap(a, b); // 题目保证是两个不同整数，统一成左小右大
        for (ll j = a; j <= b; j++) removed_tree[j] = 1; // 区域内含端点的树全部移走
    }
    // 马路上共有 L+1 个整数点，统计没被移走的
    ll ans = 0;
    for (ll i = 0; i <= L; i++)
        if (!removed_tree[i]) ans++;
    cout << ans << endl;
    return 0;
}

目录

题目描述

思路

参考代码