再学一道算法题： 种树（贪心）

种树
分数 30
作者 李廷元
单位 中国民用航空飞行学院
一条街道的一边有几座房子。因为环保原因居民想要在路边种些树，路边的地区被分割成n块，并被编号为1…n，每块大小为一个单位尺寸并最多可种一棵树。每个居民想在门前种些树并指定了三个数b，e，t这三个数分别表示该居民想在b和e之间最少种t棵树，当然，b≤e，t≤e-b+1，允许居民想种树的子区域可以交叉。出于资金紧缺的原因，环保部门请你求出能够满足所有居民的种树要求时所需要种的树的最少数量。

输入格式:
第一行为n，表示区域的个数。

第二行为h，表示房子的数目。

下面h行描述居民的需要：b、e、t(0<b≤e≤30 000，t≤e-b+1)分别用一个空格分开。

输出格式:
输出一个数，为满足所有居民的要求，所需要种树的最少数量。

输入样例:
9
4
1 4 2
4 6 2
8 9 2
3 5 2
输出样例:
5
数据规模：
30%的数据满足 0<n≤l 000；0<h≤500。
100%的数据满足 n≤30 000；h≤5 000, 0<b≤e≤30 000，t≤e-b+1。

思路：一个数组tr[j]来记录每个区间内，j位置上是否种树。贪心：从右开始种树，这样下个区间就尽可能的会有上个区间的树。
用ans来记录区间的树，与a[i].t进行比较，不满足最低要求就在tr[j]上种树，每种一棵树ans++，总计数count++，直到满足最低要求。第三个for是用来搜索区间开头到结尾的树的个数。

#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
int tr[30005];
struct node{
    int bi,ei,t;
}a[30005];
int cmp(node a,node b){
    if(a.ei==b.ei)
        return a.bi<b.bi;
    return a.ei<b.ei;
}

int main()
{
    int h,n;
    int count=0;
    memset(tr,0,sizeof tr);
    scanf("%d%d",&h,&n);
    for(int i=0;i<n;i++)
        scanf("%d%d%d",&a[i].bi,&a[i].ei,&a[i].t);
    sort(a,a+n,cmp);
    for(int i=0;i<n;i++)
    {
        int ans=0;
        for(int j=a[i].bi;j<=a[i].ei;j++)
            ans+=tr[j];
        for(int j=a[i].ei;j>=a[i].bi&&ans<a[i].t;j--)//尽量从右开始种树 
        {
            if(!tr[j])//如果tr[j]的位置上还没被种树的话，种树 
            {
                tr[j]=1;
                ans++;
                count++;
            }
        }
    }
    printf("%d",count);
    return 0;
}