#10001. 「一本通 1.1 例 2」种树（贪心）

传送门

题意：

思路：

为了使种树的数量最小，尽量让一颗树，满足多个区间，同时满足的树，一定尽可能在区间的右侧种

按右边界从小到大排序之后，我们发现，种的树越在右边，下一个区间利用的可能越大，先判断区间是否满足，当一个区间不满足时，我们就从该区间的右边界种树，直到满足即可，然后进行下一个区间

代码：

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <vector>
#include <math.h>
#include <map>
#include <queue>
#include <set>
#include <stack>
typedef long long ll;
#define PII make_pair
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
const int MAXN=3e4+50;
const int inf=0x3f3f3f3f;
const int M=5000*4;
struct sa{
    int l,r,x;
}p[MAXN];
int cmp(sa a,sa b){
    if(a.r!=b.r)return a.r<b.r;
    else return a.l<b.l;
}
int f[MAXN];//标记是否种了树
int main()
{   
    int n,h;
    scanf("%d%d",&n,&h);
    rep(i,1,h){
        scanf("%d%d%d",&p[i].l,&p[i].r,&p[i].x);
    }
    sort(p+1,p+h+1,cmp);
    memset(f,0,sizeof(f));
    int ans=0;
    rep(i,1,h){
        int cnt=0;
        rep(j,p[i].l,p[i].r)if(f[j])cnt++;
        if(cnt>=p[i].x)continue;
        per(j,p[i].r,p[i].l)if(f[j]==0){
            ans++;
            f[j]=1;
            cnt++;
            if(cnt>=p[i].x)break;
        }
    }
    printf("%d\n",ans);
    return 0;
}