P4788 绿化方案（提高）

解题思路

第一步，读懂题目。 社区有 n 条路段，每条路段最多种 1 棵树。居民给出 h 条建议，每条建议说路段 b 到 e 之间至少要种 t 棵树，区间可以交叉。问满足所有建议至少要种多少棵树。

第二步，确定贪心策略。 把建议按右端点 e 从小到大排序。处理每条建议时，先数一数它要求的区间 [b,e] 里已经种了多少棵树，如果不够 t 棵，就在这个区间里补种，补到够为止。

第三步，补种时从右往左种。 补种的树尽量种在区间的右端，也就是从 e 开始往左找空位。为什么？因为还没处理的建议，右端点都更大，种在右边的树最容易同时满足后面区间更靠右的建议，一棵树能多帮几条建议，这样种的总数最少。

第四步，为什么按 e 排序？ 右端点小的区间先处理，它的树种在最右边，就能被后面右端点更大的区间“借用”。如果先处理右端点大的区间，树种得靠左，后面的小区间用不上，就会多种树。

第五步，处理边界。 一个位置最多只能种一棵树，补种时遇到已经种过的位置要跳过，继续往左找空位。建议的区间可以交叉甚至互相包含，都要按顺序处理。

第六步，举一个例子。 n=9，建议 (1,4,2)、(3,5,2)、(4,6,2)、(8,9,2)。按 e 排序后先处理 (1,4,2)，在位置 4 和 3 种树；再处理 (3,5,2)，区间里已有 3、4 两棵，够了；再处理 (4,6,2)，已有 4 一棵，在位置 6 补一棵；最后处理 (8,9,2)，在位置 9 和 8 种两棵。一共 5 棵。

参考代码

// 绿化方案：把建议按右端点排序，每个建议先数区间里已种的树，不够就从右往左补种，种树总数最少
#include <iostream>
#include <algorithm>
using namespace std;

struct Advice {
    int b;
    int e;
    int t;
};

Advice advices[100005];

// 比较函数：右端点小的建议排在前面
bool compareEnd(const Advice &a, const Advice &b) {
    return a.e < b.e;
}

bool planted[100005];

int main() {
    int n, h;
    scanf("%d%d", &n, &h);
    for (int i = 0; i < h; i++) {
        scanf("%d%d%d", &advices[i].b, &advices[i].e, &advices[i].t);
    }
    sort(advices, advices + h, compareEnd);
    int total = 0;
    for (int i = 0; i < h; i++) {
        // 统计这个建议的区间里已经种了多少棵树
        int count = 0;
        for (int pos = advices[i].b; pos <= advices[i].e; pos++) {
            if (planted[pos]) count++;
        }
        // 如果还不够 t 棵，就从区间右端开始往左找空位补种
        for (int pos = advices[i].e; pos >= advices[i].b && count < advices[i].t; pos--) {
            if (!planted[pos]) {
                planted[pos] = true;
                count++;
                total++;
            }
        }
    }
    printf("%d\n", total);
    return 0;
}

复杂度分析

排序需要 O(h log h)。处理每条建议时，最坏要扫描整个区间统计已种树的数量，所以最坏情况总时间复杂度是 O(h 乘 n)。空间 O(n)，用一个布尔数组记录每个位置是否已经种树。