种树
题目描述： 某条街被划为 n 条路段，这 n 条路段依次编号为1…n 。每个路段最多可以种一棵树。现在居民们给出了 h 组建议，每组建议包含三个整数 b,e,t，表示居民希望在路段 b 到 e 之间至少要种 t 棵树。这些建议所给路段的区间可以交叉。请问：如果要满足所有居民的建议，至少要种多少棵树。 输入格式： 第一行为 n，表示路段数。 第二行为 h，表示建议数。 下面 h 行描述一条建议：b,e,t，用一个空格分隔。 输出格式： 输出只有一个数，为满足所有居民的建议，所需要种树的最少数量。 样例输入：
9 4 1 4 2 4 6 2 8 9 2 3 5 2
样例输出：
5
数据范围与提示：
30%的数据满足0<n<=1000,0<h<=500; 100%的数据满足0<n<=3*104,h<=5000,0<b<=e<=3*104,t<=e-b+1。
题解：先排序，为了种更少的树，我们先扫描一下该区间，看看种了多少树，如果该区间的树大于等于我们想要的树，就continue。
如果不能达到我们想要的树，就把该区间从后往前种树，直到种到我们想要的树的数量。
遍历所有区间，最后输出最少需要的树。
AC代码：
#include<stdio.h>
#include<algorithm>
using namespace std
;
struct note
{
int b
,e
,t
;
} q
[5010];
int book
[30010];
bool cmp(note x
,note y
)
{
return x
.e
<y
.e
;
}
int main()
{
int n
,h
;
scanf("%d%d",&n
,&h
);
int i
,j
;
for(i
=0; i
<h
; i
++)
scanf("%d%d%d",&q
[i
].b
,&q
[i
].e
,&q
[i
].t
);
sort(q
,q
+h
,cmp
);
int k
,tree
=0;
for(i
=0; i
<h
; i
++)
{
k
=0;
for(j
=q
[i
].b
; j
<=q
[i
].e
; j
++)
{
if(book
[j
])
k
++;
}
if(k
>=q
[i
].t
)
continue;
for(j
=q
[i
].e
; j
>=q
[i
].b
; j
--)
{
if(book
[j
]==0)
{
book
[j
]=1;
k
++;
tree
++;
if(k
==q
[i
].t
)
break;
}
}
}
printf("%d\n",tree
);
return 0;
}
