（未完待续）简单的 贪心 入门。

题目链接：LibreOJ 10001。

题目

题目描述

某条街被划为 $n$ 条路段，这 $n$ 条路段依次编号为 $1,2,\cdots,n$。每个路段最多可以种一棵树。现在居民们给出了 $h$ 组建议，每组建议包含三个整数 $b,e,t$，表示居民希望在路段 $b$ 到 $e$ 之间至少要种 $t$ 棵树。这些建议所给路段的区间可以交叉。请问：如果要满足所有居民的建议，至少要种多少棵树。

题解

思路

显然是贪心。排序以后求解即可。

代码

#include<cstdio>
#include<algorithm>
using std::sort;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
    register char ch=getchar();
    register int res=0;
    while(ch<'0'||'9'<ch)ch=getchar();
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
    return res;
}
const int MAXN=30000+5;
const int MAXH=5000+5;
struct Node{
    int b,e,t;
    void Read(void){
        b=read(),e=read(),t=read();
        //scanf("%d%d%d",&b,&e,&t);
        return;
    }
    bool operator<(const Node &a)const{
        return e<a.e;
    }
};
bool vis[MAXN];
int n,h;
Node I[MAXH];
int main(void){
    register int i,j,sum;
    n=read(),h=read();
    //scanf("%d%d",&n,&h);
    for(i=1;i<=h;++i)
        I[i].Read();
    sort(I+1,I+h+1);
    for(i=1;i<=h;++i){
        sum=0;
        for(j=I[i].b;j<=I[i].e;++j)
            sum+=(int)vis[j];
        if(sum<I[i].t){
            sum-=I[i].t;
            for(j=I[i].e;j>=I[i].b;--j){
                if(!vis[j]){
                    vis[j]=true;
                    ++sum;
                    if(!sum)
                        break;
                }
            }
        }
    }
    sum=0;
    for(i=1;i<=n;++i)
        sum+=(int)vis[i];
    printf("%d\n",sum);
    return 0;
}