「一本通 1.1 例 2」种树

题目描述

编号 $1 \sim N$ 的地块每块最多种一棵树， $M$ 个需求各给出 $B, E, T$ ，要求区间 $[B,E]$ 内至少种 $T$ 棵树（区间可交叉）。求最少种多少棵，并输出每棵树的位置。

思路

经典区间贪心：把所有区间按右端点 $E$ 升序排序，逐个统计区间内已有的树数，不足则从右端点向左补种到空位置上。因为后面处理的区间右端点都不小于当前区间，靠右种树最容易被后续区间复用，所以总量最少。

参考代码

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
45
46
47
48
49
50
51
52
53
54
55
56
57#!/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-05 21:47
# update_at: 2026-07-05 21:47

import sys

# 区间三元组类型：(起始位置 b, 结束位置 e, 至少种树数 t)
Interval = tuple[int, int, int]


def min_trees(intervals: list[Interval], max_pos: int) -> int:
    """计算满足所有区间要求所需的最少树木总数。

    按区间右端点从小到大贪心排序：为了尽量复用给后续区间，
    每个区间缺少的树木优先从右向左紧挨着右端点放置。
    """
    # 状态数组：planted[pos] 为 True 表示位置 pos 已种树（1-indexed）
    planted = bytearray(max_pos + 1)
    total_trees = 0

    # 优先按结束位置 e 升序排序
    for b, e, t in sorted(intervals, key=lambda iv: iv[1]):
        # 统计当前区间 [b, e] 内已经种了多少棵树
        current_count = sum(planted[p] for p in range(b, e + 1))
        need = t - current_count
        if need <= 0:
            continue

        # 从右端点向左贪心补齐缺少的树
        for p in range(e, b - 1, -1):
            if not planted[p]:
                planted[p] = 1
                total_trees += 1
                need -= 1
                if need == 0:
                    break

    return total_trees


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data, None)
    if n is None:
        return
    h = next(data)  # 居民需求条数（区间数）
    intervals: list[Interval] = [(next(data), next(data), next(data)) for _ in range(h)]

    ans = min_trees(intervals, n)
    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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75/**
 * 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 23:23
 * update_at: 2026-10-05 23:23
 */
// main.cpp：「一本通 1.1 例 2」种树，区间贪心：按右端点排序，缺树时从右往左补种。
// 输出最少种树数以及每棵树的位置。

#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXN = 30005; // 地块数上限
const int MAXM = 5005;  // 居民需求数上限

// 一条居民需求：区间 [b, e] 内至少种 t 棵树
struct Demand {
    ll b, e, t;
};

ll n, m;
Demand d[MAXM];
bool planted[MAXN]; // planted[pos] = true 表示位置 pos 已种树

// 贪心比较：按区间右端点 e 从小到大排序
bool cmp_e(const Demand &a, const Demand &b) {
    return a.e < b.e;
}

int main() {
    scanf("%lld %lld", &n, &m);
    for (int i = 1; i <= m; i++)
        scanf("%lld %lld %lld", &d[i].b, &d[i].e, &d[i].t);

    // 右端点小的区间先处理，后面的区间才能复用靠右种的树
    sort(d + 1, d + m + 1, cmp_e);

    ll total = 0; // 总共种下的树数
    for (int i = 1; i <= m; i++) {
        // 先统计当前区间 [b, e] 内已经种了多少棵
        ll has = 0;
        for (ll p = d[i].b; p <= d[i].e; p++)
            if (planted[p])
                has++;

        // 还缺 need 棵，从右端点向左找空位补种，
        // 靠右种最容易被后面的区间复用
        ll need = d[i].t - has;
        for (ll p = d[i].e; p >= d[i].b && need > 0; p--) {
            if (!planted[p]) {
                planted[p] = true;
                total++;
                need--;
            }
        }
    }

    printf("%lld\n", total);
    // 逐棵输出位置，位置之间用空格分隔，行尾不留多余空格
    bool first = true;
    for (ll p = 1; p <= n; p++)
        if (planted[p]) {
            if (first) {
                printf("%lld", p);
                first = false;
            } else
                printf(" %lld", p);
        }
    printf("\n");
    return 0;
}

「一本通 1.1 例 2」种树

目录

题目描述

思路

参考代码