种树

https://loj.ac/problem/10001

题目描述

  给定(h)个闭区间([s_i,t_i])，以及每段区间内最少点的个数，求使每个区间都满足条件时最小总点数。

思路

  区间选点问题可以用一个很经典的方法，就是将区间按右端点升序排序，选取区间最右边的点一定最优。那么与那道题类似，我们可以以相同的方式进行排序，再顺序循环区间，查找这个区间内点的个数，若已满足条件，就继续循环；否则就从最右的点开始倒序循环，看能否种树，直到符合条件。这个贪心策略的正确性是显然的，因为排序后要使该区间内的点达到最大的利用，使结果最小，就应该种在最后。

代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN=30020;
struct aa
{
    int b,e,t;
}a[MAXN];
bool f[MAXN];
bool cmp(aa x,aa y)
{
    if(x.e!=y.e)return x.e<y.e;
    else return x.b<y.b;
}
int main() 
{
    int n,h;
    scanf("%d%d",&n,&h);
    for(int i=0;i<h;i++)
        scanf("%d%d%d",&a[i].b,&a[i].e,&a[i].t);
    sort(a,a+h,cmp);
    int ans=0;
    for(int i=0;i<h;i++)
    {
        int s=0;
        for(int j=a[i].b;j<=a[i].e;j++)
            if(f[j])s++;
        if(s>=a[i].t)continue ;
        for(int j=a[i].e;j>=a[i].b;j--)
            if(!f[j])
            {
                f[j]=1;
                ans++;s++;
                if(s==a[i].t)break ;
            }
    }
    printf("%d",ans);
    return 0;
}