20190511题解

MSTBL · 2019-05-18 08:01:30 · 个人记录

T1 种树

【题目描述】 某条街被划为n条路段，这n条路段依次编号为1,2,…,n。每个路段最多可以种一棵树。现在居民们给出了h组建议，每组建议包含三个整数b,e,t，表示居民希望在路段b到e之间至少要种t棵树。这些建议所给路段的区间可以交叉。请问：如果要满足所有居民的建议，至少要种多少棵树。 【输入格式】 第一行为n，表示路段数。 第二行为h，表示建议数。 下面h行描述一条建议：b,e,t，用一个空格分隔。 【输出格式】 输出只有一个数，为满足所有居民的建议，所需要种树的最少数量。 【样例输入】 tree.in 9 4 1 4 2 4 6 2 8 9 2 3 5 2 【样例输出】 tree.out 5 【说明】 30%的数据满足 0<n<=1000，0<h<=500； 100%的数据满足 0<n<=3104，h<=5000，0<b<=e<=3104，t<=e-b+1

这是一道贪心题。种树显然种在区间相交的地方最好。当时想着要重复越多的地方越先种，其实并不用那么复杂。对于每一个区间，在它尽可能多的相交的地方种上树，就能得到最优解。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <cstdlib>
using namespace std;

struct seg
{
    int x, y, c; //x是起点，y是终点，c是要种的树的数量
} a[210000];

int n = 0, h = 0, ans = 0;
bool plant[210000] = {0}; //plant记录是否种了树

bool cmp(seg n1, seg n2)
{
    return n1.y > n2.y;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> n;
    for (int i = 1; i <= h; i++)
    {
        cin >> a[i].x >> a[i].y >> a[i].c;
    }

    sort(a + 1, a + h + 1, cmp);

    for (int i = 1; i <= h; i++)
    {
        int t = 0; //记录当前区间已经种过的树
        for (int j = a[i].x; j <= a[i].y; j++)
        {
            if (plant[j] == true)
            {
                t++;
            }
        }

        if (t >= a[i].c) //已种过的树已经达到目标就到下一个区间，没有就继续
            continue;

        for (int j = a[i].y; j >= a[i].x; j--) //从后往前遍历，没种过树的地方种上，因为之前按区间终点升序排序过，这样就能得到最优解
        {
            if (!plant[j])
            {
                t++;
                ans++;
                plant[j] = true;
                if (t == a[i].c)
                    break;
            }
        }
    }
    cout << ans << endl;
    //system("pause");
    return 0;
}