【贪心】种树_牛客博客

今晚把困扰了好久的贪心题做出来了，给大家分享一下思路。

题目描述

一条街的一边有几座房子。因为环保原因居民想要在路边种些树。路边的地区被分割成块，并被编号成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。

输出

树的数目。

样例输入

复制样例数据

样例输出

贪心性质:尽可能少的种树，重复部分越多越好，故先按起始位置排序，具体代码如下：

#include <stdio.h>
#include <algorithm>
#include <stdlib.h>
#include <iostream>
using namespace std;
struct tree
{
    int B;
    int E;
    int T;
}t[50000];
bool cmp(tree a,tree b)
{
    return a.B<b.B;
}
int main()
{
    int cnt=0;
    int m,n;
    int H;
    scanf("%d%d",&n,&H);
    for(int i=1;i<=H;i++)
        scanf("%d%d%d",&t[i].B,&t[i].E,&t[i].T);
    sort(t+1,t+H+1,cmp);
    int z=t[1].E;
    cnt+=t[1].T;//第一个起始位置最靠前可以想象成从后往前排，想种多少种多少。
    for(int i=2;i<=H;i++)
    {
        if(t[i].B<=z)//判断是否可以重复
        {
            if(t[i].E<=z)//如果是他的一个子区间
            {
                if(t[i-1].T>=t[i].T)
                    continue;
                else
                    cnt+=t[i].T-t[i-1].T;
            }
            else
            {
                int ans=z-t[i].B+1;//从第下一个的开始到上一个的结束可以种多少
                if(ans>=t[i].T)//可以种下，则重复部分最大
                    continue;
                else
                {
                    cnt+=t[i].T-ans;//否则补上差的数
                    z=z+t[i].T-ans;//末位置改变
                }
            }
        }
        else//不可以重复直接加就可以了。
        {
            cnt+=t[i].T;
            z=t[i].E;//末点位置改变。
        }
    }
    printf("%d\n",cnt);
    return 0;
}

简单代码，大神勿喷。