算法学习日记 2021/4/23——01

学习日记-01
根据题目所给，可以推断出局部最优解就是从每个区间的最后往前种树。

#include<iostream>
#include<algorithm>
using namespace std;
struct line { int l, r, cnt; }a[5010];

bool cmp(line x,line y)
{
    return x.r < y.r;
}
int n, h;

bool used[30010] = { 0 };

void Init()
{
    cin >> n >> h;
    for (int i = 1; i <= h; i++)
    {
        cin >> a[i].l >> a[i].r >> a[i].cnt;
    }
    sort(a + 1, a + h + 1,cmp);
}

void solve()
{
    int k,ans=0;
    for(int i = 1; i <= h; i++)
    {
        k = 0;
        for (int j = a[i].l; j <= a[i].r; j++)
        {
            if (used[j])
            {
                k++;
            }
        }
        if (k >= a[i].cnt) continue;
        else
        {
            for (int j = a[i].r; j >= a[i].l; j--)
            {
                if (!used[j]) 
                {
                    used[j] = 1;
                    k++;
                    ans++;
                    if (k == a[i].cnt)
                        break;
                }
            }
        }
    }
    cout << ans << endl;
}

int main()
{
    Init();
    solve();
    return 0;
}