P1250种树

P1250种树

题面：

题目描述

路边的地区被分割成块，并被编号成 1,2,…,n。每个部分为一个单位尺寸大小并最多可种一棵树。

每个居民都想在门前种些树，并指定了三个号码 b，e，t。这三个数表示该居民想在地区 b 和 e 之间（包括 b 和 e）种至少 t 棵树。

居民们想种树的各自区域可以交叉。你的任务是求出能满足所有要求的最少的树的数量。

输入格式

输入的第一行是一个整数，代表区域的个数 n。

输入的第二行是一个整数，代表房子个数 h。

第 3 到第 (h + 2) 行，每行三个整数，第 (i + 2) 行的整数依次为 bi, ei, ti，代表第 i 个居民想在 bi​ 和 ei​ 之间种至少 ti​ 棵树。

输出格式

输出一行一个整数，代表最少的树木个数。

思路：贪心

我们可以从右端点最靠左的线段开始，当遇到树木个数没有达到ti，就从最末端没树的地方种（ti-现有的个数）棵，就可以尽量满足后面的线段。

代码如下：

#include<bits/stdc++.h>
using namespace std;
struct node
{
    long long left,right,num,ans;
}a[30010];
long long n,ans2=0,m;
bool b[30010];
inline bool cmp(node x,node y)
{
    return x.right<y.right;
}
int main()
{
    cin>>m>>n;
    for(int i=1; i<=n; i++)
    {
        cin>>a[i].left>>a[i].right>>a[i].num;
    }
    sort(a+1,a+n+1,cmp);
    for(int i=1; i<=n; i++)
    {
        for(int j=a[i].left; j<=a[i].right; j++)
        {
            if(b[j])
            {
                a[i].ans++;
            }
        }
        if(a[i].ans>=a[i].num)
        {
            continue;
        }
        for(int k=a[i].right; k>=a[i].left; k--)
        {
            if(a[i].ans==a[i].num)
            {
                break;
            }
            if(b[k]==0)
            {
                b[k]=1;
                a[i].ans++;
                ans2++;
            }
        }
    }
    cout<<ans2;
    return 0;
}