1423：【例题2】种树

时间限制: 1000 ms 内存限制: 65536 KB
提交数: 3411 通过数: 1374
【题目描述】
现在我们国家开展新农村建设，农村的住房建设纳入了统一规划，统一建设，政府要求每一住户门口种些树。门口路边的地区被分割成块，并被编号成1..N。每个部分为一个单位尺寸大小并最多可种一棵树。每个居民房子门前被指定了三个号码B，E，T。这三个数表示该居民想在B和E之间最少种T棵树。当然，B≤E，居民必须记住在指定区不能种多于区域地块数的树，所以T≤E-B+l。居民们想种树的各自区域可以交叉。你的任务是求出能满足所有要求的最少的树的数量，尽量较少政府的支出。

【输入】
第一行包含数据N，M，区域的个数(0<N≤30000)，房子的数目(0<m≤5000)；

下面的m行描述居民们的需要：B E T，0<B≤E≤30000，T≤E-B+1。

【输出】
输出一个数，为满足所有居民的要求，所需要种树的最少数量。

【输入样例】
9 4
3 5 2
1 4 2
4 6 2
8 9 2
【输出样例】
5

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

/*
    不要有Bug啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊 
*/




struct task{
    int begin;
    int end;
    int num;
};


bool operator < (const task A,const task B)
{
    if(A.end!=B.end)
        return A.end<B.end;
    else
    if(A.begin!=B.begin)
        return A.begin<B.begin;
    else
    if(A.num!=B.num)
        return A.num<B.num;
}

int tree[30000];
task list[5001];

int main()
{
    int N,M;cin>>N>>M;
    memset(list,0,sizeof(list));
    memset(tree,0,sizeof(tree));
    
    for(int i=0;i<M;i++)
    {
        cin>>list[i].begin>>list[i].end>>list[i].num;    
    }
    sort(list,list+M);

    for(int i=0;i<M;i++)
    {
        int k=0;
        for(int j=list[i].end;j>=list[i].begin;j--)
        {
            if(tree[j]!=0)
                k++;
            }    
        if(k>=list[i].num)
            continue;
            list[i].num-=k;    
        for(int j=list[i].end;j>=list[i].begin;j--)
        {
            if(tree[j]==0)
                if(list[i].num>0)
                {
                    tree[j]++;
                        list[i].num--;
                }
        }
    }
    int cnt=0;
    for(int i=0;i<=N;i++)
        cnt+=tree[i];
    cout<<cnt;
    return 0;
}