洛谷P1250 种树黄题

本是古典何须时尚 2021-11-22 04:50 305阅读 0赞

洛谷黄题（[点击跳转][Link 1]）

**题目描述:**

一条街的一边有几座房子。因为环保原因居民想要在路边种些树。路边的地区被分割成块，并被编号成1..N。每个部分为一个单位尺寸大小并最多可种一棵树。每个居民想在门前种些树并指定了三个号码B，E，T。这三个数表示该居民想在B和E之间最少种T棵树。当然，B≤E，居民必须记住在指定区不能种多于区域地块数的树，所以T≤E-B+l。居民们想种树的各自区域可以交叉。你的任务是求出能满足所有要求的最少的树的数量。写一个程序完成以下工作：

## 输入输出格式 ##

输入格式：

第一行包含数据N，区域的个数(0<N≤30000)；

第二行包含H，房子的数目(0<H≤5000)；

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

输出格式：

输出文件只有一行写有树的数目

## 输入输出样例 ##

输入样例\#1：

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

输出样例\#1：

**解析**

很明显，这是一道贪心加排序的题，就是n个树，还有一大堆的区间。弄了好半天，才知道是从右端点往左端点枚举。大家不要犯与我一样的错误。

然后上代码：

**代码**

#include<bits/stdc++.h>
    using namespace std;
    struct tree
    {
        int b,e,t;
    }a[30001];
    int n,h,ans;
    bool m[30001];
    bool cmp(tree x,tree y)
    {
        return x.e<y.e;
    }
    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,cmp);
        for(int i=1;i<=h;i++)
        {
            int cnt_ans=0;
            for(int j=a[i].b;j<=a[i].e;j++)
            {
                if(m[j]) cnt_ans++; 
            }
            if(cnt_ans>=a[i].t) continue;
            for(int j=a[i].e;j>=a[i].b;j--)
            { 
                if(!m[j])
                { 
                    m[j]=1;
                    cnt_ans++;
                    ans++;
                    if(cnt_ans==a[i].t) break;
                }
            }
        }
        cout<<ans;
        return 0;
    }

转载于:https://www.cnblogs.com/weilinxiao/p/11157687.html

[Link 1]: https://www.luogu.org/problemnew/show/P1250