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; }