种树

题目描述

一条街的一边有几座房子。因为环保原因居民想要在路边种些树。路边的地区被分割成块，并被编号成1..N。每个部分为一个单位尺寸大小并最多可种一棵树。每个居民想在门前种些树并指定了三个号码B，E，T。这三个数表示该居民想在B和E之间最少种T棵树。当然，B≤E，居民必须记住在指定区不能种多于区域地块数的树，所以T≤E-B+l。居民们想种树的各自区域可以交叉。你的任务是求出能满足所有要求的最少的树的数量。

写一个程序完成以下工作：

输入输出格式

输入格式：

第一行包含数据N，区域的个数(0<N≤30000)；

第二行包含H，房子的数目(0<H≤5000)；

下面的H行描述居民们的需要：B E T，0<B≤E≤30000，T≤E-B+1。

输出格式：

输出文件只有一行写有树的数目

9
4
1 4 2
4 6 2
8 9 2
3 5 2

输出样例#1：

5

题面是我从别人的csdn上复制下来的

看洛谷上的题解别人都是用差分约束做的
但我偏不，我就用贪心（因为我不会差分约束啊）
按照区间末端点的大小排序，开一个数组记录这个位置上是否被放树
如果之前的区间与当前区间的重叠部分有>=t棵树，那就直接跳过这个区间
如果不够t棵，就在这个区间的结尾出从后往前放置剩下的树，因为这样对之后答案的贡献更大。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int n,h,ans = 0;
struct node{
    int b,e,v;
}a[5003],mid;
int f[30003];
int cmp(node x,node y)
{
    return x.e < y.e;
}
int main()
{
    scanf("%d%d",&n,&h);
    memset(f,0,sizeof(f));
    for(int i = 1;i <= h;i++)
    {
        scanf("%d%d%d",&a[i].b,&a[i].e,&a[i].v);
    }
    sort(a + 1,a + h + 1,cmp);
    for(int i = 1;i <= h;i++)
    {
        int k = 0;
        for(int j = a[i].b;j <= a[i].e;j++) 
        {
            if(f[j] == 1)k++;
        }
        if(k >= a[i].v)continue;
        for(int j = a[i].e;j >= a[i].b;j--)
        { 
            if(f[j] == 0)//只有当这个位置没有放树时才能放 
            {
             f[j] = 1;
             ans++;
             k++;
             if(k == a[i].v)break;
   }
        }
    }
    printf("%d",ans);
    return 0;
}