loj10001种树

好久不写博客了，发现不好找做过和题！还得接着写啊！

------------------------------------------------------------------

题目描述

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

输入格式

第一行为n ，表示路段数。

第二行为 h，表示建议数。

下面 h 行描述一条建议：b,e,t，用一个空格分隔。

输出格式

输出只有一个数，为满足所有居民的建议，所需要种树的最少数量。

样例

样例输入

样例输出

数据范围与提示

的数据满足 n<=1000，h<=500；

的数据满足 n<=3e4，h<=5e3，b,e<=3e4，t<=e-b+1。

---------------------------------------------------------------------------------------

原来这个题是按差分约束做的，没有向贪心方向想，可是贪心也可以。

所有的建议按e排序，这样明显树应当靠后种，这样树更可能处在重叠区，可以节省树。

这样方法就明显了。首先建议按e排序，然后依次处理每一个建议，统计每个建议区间内已经种了多少树，够了就不用再处了。如果不够，那么就要从后向前找到没种树的点种树，直到建议区间内的树的数量满足要求为至。

----------------------------------------------------------------------------------------

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 const int maxn=3e4+10;

 4 const int maxm=5e3+10;

 5 int n,m;

 6 struct node

 7 {

 8     int b,e,t;

 9 }sz[maxm];

10 int qj[maxn];

11 bool cmp(node a,node c)

12 {

13     return a.e<c.e;

14 }

15 int main()

16 {

17     scanf("%d%d",&n,&m);

18     for(int i=1;i<=m;++i)

19         scanf("%d%d%d",&sz[i].b,&sz[i].e,&sz[i].t);

20     sort(sz+1,sz+1+m,cmp);

21     int ans=0;

22     for(int i=1;i<=m;++i)

23     {

24         int tj=0;

25         for(int j=sz[i].e;j>=sz[i].b;--j)

26         {

27             if(qj[j])tj++;

28             if(tj>=sz[i].t)break;

29         }

30         if(tj<sz[i].t)

31         for(int j=sz[i].e;j>=sz[i].b;--j)

32         {

33             if(qj[j]==0)qj[j]=1,++ans,++tj;

34             if(tj>=sz[i].t)break;

35         }

36     }

37     cout<<ans;

38     return 0;

39 }

巴特西