1423：【例题2】种树

时间限制: 1000 ms         内存限制: 65536 KB

【题目描述】

【输入】

【输出】

【输入样例】

9 4
3 5 2
1 4 2
4 6 2
8 9 2

【输出样例】

5

解析： 对于每个区间按右端点从小到大排序，对于每个区间，如果已有树木数量不满足要求，从右端点忘前种树，直到符合要求，最后统计树的数量，详见代码：

#include<bits/stdc++.h>
using namespace std;
bool b[30005];//b[i]表示第i个位置是否种树
struct node {
    int b;//开始点
    int e;//结束点
    int t;//至少t棵树
    bool operator < (const node &x) const{
        return e<x.e;
    }
}a[5005];//区间数组
int n,h;
int ans=0;
int main() {
    cin>>n>>h;
    for(int i=1;i<=h;i++){
        cin>>a[i].b>>a[i].e>>a[i].t;
    }
    sort(a+1,a+h+1);//按区间右端点从小到大排序
    for(int i=1;i<=h;i++){
        int cnt=0;
        for(int j=a[i].b;j<=a[i].e;j++){//统计区间内已有的树的数量
            if(b[j]) cnt++;
        }
        if (cnt>=a[i].t) continue;//满足条件，继续下一个区间
        cnt=a[i].t-cnt;//算出缺多少树
        for(int j=a[i].e;j>=a[i].b;j--){//从区间右端点向左端点种树
            if (b[j]==0){
                b[j]=1;
                cnt--;
                if (cnt==0) break;//满足条件，不再种树
            }
        }
    }
    for(int i=1;i<=n;i++){//统计种了多少树
        if (b[i]) ans++;
    }
    cout<<ans;
    return 0;
}