[Loj#10001]种树

discription:
某条街被划为\(n\)条路段，这\(n\)条路段依次编号为\(1\)~\(n\) 。每个路段最多可以种一棵树。现在居民们给出了\(h\)组建议，每组建议包含三个整数\(b,e,t\) ，表示居民希望在路段\(b到e\)之间至少要种t棵树。这些建议所给路段的区间可以交叉。请问：如果要满足所有居民的建议，至少要种多少棵树。
solution:
把尽量多的树种在重合的区间内, 考虑按照区间右端排序, 自右至左种新树.
code:

#include<cstdio>
#include<algorithm>
const int N(30001);
bool f[N];
struct range { int l, r, t; }q[5000];
int main() {
	int n, h; scanf("%d%d", &n, &h);
	for (int i = 0; i < h; ++i)
		scanf("%d%d%d", &q[i].l, &q[i].r, &q[i].t);
	std::sort(q, q + h, [](range& a, range& b) {return a.r < b.r; });
	int ans = 0;
	for (int i = 0; i < h; ++i) {
		for (int j = q[i].l; q[i].t && j <= q[i].r; ++j) if (f[j])--q[i].t;
		for (int k = q[i].r; q[i].t; --k) if (!f[k])--q[i].t, f[k] = 1, ++ans;
	}
	printf("%d\n", ans);
}

[Loj#10001]种树

原文：https://www.cnblogs.com/dwt2021/p/14410176.html