洛谷题单指南-贪心-P5019 [NOIP2018 提高组] 铺设道路

原题链接：https://www.luogu.com.cn/problem/P5019

题意解读：最短时间内填满道路，连在一起的不为0的坑可以一起填

解题思路：

方法1：分治法

对于一段连续不同深度的坑，可以最多连续填的天数是最小深度

在填满最小深度之后，分别针对其左边和右边的区域再进行填充，这就是此题分治法的理论基础。

因此，可以遍历每一个坑，跳过深度是0的坑，把这些坑分组

对于每一组，找到深度最小值，填充直到最小深度被填满，即答案加上最小深度

然后对该组每一个坑，减去被填充的深度（即最小深度），递归处理该区域

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;

int d[N], n;
long long ans;

//填充l~r之间的道路，filled表示l~r之间已被填充的深度
void fill(int l, int r, int filled)
{
    bool full = true; //已经填满
    for(int i = l; i <= r; i++) //把已经填的部分减掉
    {
        d[i] -= filled;
        if(d[i]) full = false;
    }
    if(full) return;

    for(int i = l;i <= r; i++)
    {
        int minx = 1e9; 
        int j = i;
        while(d[j] && j <= r) //寻找连续不为0的区间，记录最小值
        {
            minx = min(minx, d[j]);
            j++;
        }
        ans += minx; //可以连续填充直到最小深度填满，即填充天数加上最小深度
        if(i < j) fill(i, j - 1, minx); //递归处理剩下的部分
        
        if(j > r) break;

        i = j;
    }
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> d[i];

    fill(1, n, 0);
    cout << ans;

    return 0;
}

方法2：递推法

从第1个坑开始，如果后一个的深度比前一个深度小，则填充天数不变（为第一个坑的深度）

如果后一个坑的深度比前一个坑的深度大，则填充天数要增加： 后一个坑的深度-前一个坑的深度

依次比较每个相邻高度深度，最后加上第一坑的深度，即得到答案。

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;

int a[N], n;
long long ans;

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];

    for(int i = 2; i <= n; i++)
    {
        if(a[i] > a[i - 1]) ans += a[i] - a[i - 1];
    }
    ans += a[1];
    cout << ans;

    return 0;
}