题解 | #种树#

思路：贪心思想，要想尽可能地少种树，就要在之前已经种过，才会使此次种树量最少，那就是对右端点从小到大排序从后往前种树为最优解，至于按照上一区间的右端点大于这一去点的左端点会使答案可能变大比如1 6 2 与 2 3 1 这两组数据实际最小是两棵树但按照那个排序会是三棵树，具体代码如下

#include <iostream>
#include <algorithm>
using namespace std;
struct w 
{
    int l;
    int r;
    int s;
};
struct w a[30005];
bool cmp(struct w x,struct w y)
{
    return x.r<y.r;
}
int v[30005];
int main()
{
    int n;
    cin>>n;
    int h;
    cin>>h;
    for(int i=0;i<h;i++)
    {
        cin>>a[i].l>>a[i].r>>a[i].s;
    }
    long long ans=0;
    sort(a,a+h,cmp);
    for(int i=0;i<h;i++)
    {
        int cnt=a[i].s,r1=a[i].r;
        while(r1>=a[i].l&&cnt>0) //判断此时需要种的树是否之前种过
        {
            if(v[r1]==1)
                cnt--;
            r1--;
        }
        ans+=cnt;  //每次都是剩余数量是需要一定种的的树
        if(cnt!=0)
        {
            r1=a[i].r;
            while(cnt>0)
            {
                if(v[r1]==0)   //从后往前种树
                {
                    v[r1]=1;
                    cnt--;
                }
                r1--;
            }
        }
    }
    cout<<ans;
    return 0;
}