题解：P5019 [NOIP2018 提高组] 铺设道路

glass_goldfish · 2024-12-25 18:36:53 · 题解

这题是一道比较简单的贪心。

我们发现，如果 a_{i-1}\le a_{i}，那么 a_{i-1} 肯定会被在填 a_i 的时候顺带一起被填掉，但是还是要填 a_i-a_{i-1} 的深度（因为还要把 a_i 填掉）。建立变量 ans，依次枚举即可。但是要注意，按照这种方法，第一次直接要把 a_1 填了，所以 ans 的初始值为 a_1。

代码：

#include<bits/stdc++.h>
#define int long long
#define INF 0x3f3f3f
using namespace std;
int n,a[300001];
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    int ans=a[1];
    for(int i=2;i<=n;i++)
        if(a[i]>=a[i-1])
            ans+=(a[i]-a[i-1]);
    cout<<ans;
    return 0;
}