种树

似乎又想到3紫1黑

其实是两道不相关的题目，区间选点问题，给了我们O(N)的复杂度，那就很好确定了，我们可以考虑尽量让一棵树发挥最大价值，放在尾部，直到满足要求为止。

具体实现

1. 用右端点递增排序
2. 将不够的树补在尾部
3. 直到补满

Code

#include<bits/stdc++.h>
using namespace std;
int b[30005],h,ans,n;
struct node{int s,t,f;}a[5001];
bool cmp(node a,node b){return a.t<b.t;}
int main(){
    scanf("%d%d",&h,&n);
    for(int i=1;i<=n;i++)
     scanf("%d %d %d",&a[i].s,&a[i].t,&a[i].f);//输入
    sort(a+1,a+n+1,cmp);//按照右端点排序
    for(int i=1;i<=n;i++){
        int sum=0;
        for(int j=a[i].s;j<=a[i].t;++j)sum+=b[j];//算出已经种了多少树
        if(sum>=a[i].f)continue;//如果超过需求就跳过
        sum=a[i].f-sum;//剩余量
        for(int j=a[i].t;j>=a[i].s,sum;--j,--sum){//种在尾部
         while(b[j])--j;b[j]=1;++ans;//种了一棵树
        }
    }
    cout<<ans<<endl;
}