种树

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

按要求区间右端点升序处理，若区间内树数不足，就从右往左补树。

OJ: luogu

题目 ID: P1250

难度:普及/提高-

标签:贪心区间覆盖树状数组

日期: 2026-06-22 21:17

目录

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

题意

有 n 个位置，每个位置最多种一棵树。

给出若干要求 [l,r,need]，表示区间 [l,r] 内至少要种 need 棵树。

求满足所有要求的最少种树数量。

思路

先看一个可以直接验证想法的朴素解：

cpp
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 25;

struct Request {
    int l;
    int r;
    int need;
};

int n, h;
Request req[MAXN];

bool check_mask(int mask) {
    for (int i = 1; i <= h; i++) {
        int cnt = 0;
        for (int pos = req[i].l; pos <= req[i].r; pos++) {
            if (mask & (1 << (pos - 1))) {
                cnt++;
            }
        }
        if (cnt < req[i].need) {
            return false;
        }
    }
    return true;
}

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

    cin >> n;
    cin >> h;
    for (int i = 1; i <= h; i++) {
        cin >> req[i].l >> req[i].r >> req[i].need;
    }

    int ans = n + 1;
    for (int mask = 0; mask < (1 << n); mask++) {
        if (check_mask(mask)) {
            ans = min(ans, __builtin_popcount((unsigned)mask));
        }
    }

    cout << ans << '\n';
    return 0;
}

暴力会枚举哪些位置种树，再检查所有区间要求。这个做法只能用于小数据。

贪心做法：按区间右端点从小到大处理要求。

当处理区间 [l,r] 时，如果里面已有树数不足，就必须在这个区间中补树。为了尽量帮助后面的区间，应该从 r 开始向左补。

原因是后面的区间右端点不会更小，靠右的位置更可能被后续区间继续利用；而靠左的位置对未来帮助不会更大。

用树状数组维护当前某个区间里已经种了多少棵树。

代码

cpp
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 30005;
const int MAXH = 5005;

struct Request {
    int l;
    int r;
    int need;
};

int n, h;
Request req[MAXH];
int tree_bit[MAXN];
bool planted[MAXN];

bool cmp_request(const Request &a, const Request &b) {
    if (a.r != b.r) {
        return a.r < b.r;
    }
    return a.l > b.l;
}

void bit_add(int pos, int val) {
    while (pos <= n) {
        tree_bit[pos] += val;
        pos += pos & -pos;
    }
}

int bit_sum(int pos) {
    int res = 0;
    while (pos > 0) {
        res += tree_bit[pos];
        pos -= pos & -pos;
    }
    return res;
}

int range_sum(int l, int r) {
    return bit_sum(r) - bit_sum(l - 1);
}

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

    cin >> n;
    cin >> h;
    for (int i = 1; i <= h; i++) {
        cin >> req[i].l >> req[i].r >> req[i].need;
    }

    sort(req + 1, req + h + 1, cmp_request);

    int ans = 0;
    for (int i = 1; i <= h; i++) {
        int have = range_sum(req[i].l, req[i].r);
        int lack = req[i].need - have;
        for (int pos = req[i].r; lack > 0 && pos >= req[i].l; pos--) {
            if (!planted[pos]) {
                planted[pos] = true;
                bit_add(pos, 1);
                ans++;
                lack--;
            }
        }
    }

    cout << ans << '\n';
    return 0;
}

复杂度

排序为 O(hlogh)O(h log h)。

每次查询和每次补树更新都是 O(logn)O(log n)，总补树次数不超过 n。

总复杂度：

text
O((h+n) log n)

空间复杂度为 O(n+h)O(n+h)。

总结

本题的贪心关键是“当前必须补的树，尽量补在右边”。

按右端点排序保证之前的要求不会被破坏，而从右补树能最大化对未来区间的复用机会。