2019暑假集训种树

qxds 2019-07-10 原文

题目描述

一条街道的一边有几座房子，因为环保原因居民想要在路边种些树，路边的居民被分割成 n 块，并被编号为 1…n。每块大小为一个单位尺寸并最多可种一棵树。每个居民想在门前种些树并指定了三个数b,e,t。这三个数分别表示该居民想在b和e之间最少种t棵树，当然b≤e，t≤e-b+1，允许居民想种树的子区域可以交叉。出于资金紧缺的原因，环保部门请你求出能够满足所有居民的种树要求时所需要种的树的最少数量。

输入

第一行为 n，表示区域的个数。
第二行为 h，表示房子的数目。
下面 h 行描述居民的需要：b,e,t（0＜b≤e≤30000，t≤e-b+1）分别用一个空格分开。

输出

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

样例输入

样例输出

提示

30% 的数据满足 0<n≤1000，0<h≤500；
100% 的数据满足 0<n≤3×10^4，h≤5000，0<b≤e≤3×10^4 ，t≤e−b+1。

明显的贪心有兴趣的同学可以参见类似题目会场安排

为了种植更多的树，我们希望将树尽可能种在区间之间的交叉点上，也就是说当我们按照左边界从小到大排序所有区间时，应该尽可能将树种植在右边界上（为了尽量和下一个区间的左边界重合）

上代码

#include<iostream>
#include<algorithm>
using namespace std;
int n,h,book[30050],ans;
struct node
{
    int b,e,t;
    bool operator<(const node& o) const
    {
        return e<o.e;
    }
}a[5005];//区间
int main()
{
    scanf("%d%d",&n,&h);
    for(int i=1;i<=h;i++)scanf("%d%d%d",&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(book[j])cnt++;//统计上个区间种在右边界上的树是否足够本区间要去
        if(cnt>=a[i].t)continue;
        for(int j=a[i].e;j>=a[i].b;j--)
        {
            if(book[j]==0)
            {
                book[j]=1;
                cnt++;
                if(cnt==a[i].t)break;            
            }//不够的补在右区间
        }
    }
    for(int i=1;i<=n;i++)
        if(book[i])ans++;
    printf("%d",ans);
    return 0;
}