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

别人内卷我在躺平 · 2024-12-25 18:59:00 · 题解

本题算法为贪心。

我们可以先来分析一下样例: 我们可以先用差分的思想把相邻两段路的陷深度算出来，然后去枚举差。我们要使操作次数越少就必须要以陷深度较小的路为标准，把它们的差填满，否则会浪费次数。如果 a_i>a_{i-1} , 也就是可以以 a_i 作为标准把 a_{i-1} 的陷深度减少 cha_{i}。

注意：若果 a_i=a_i-1 就不能变化，因为有可能后面的路可以连着这些路一起移平。

#include<bits/stdc++.h>
using namespace std;
int a[1000005],cha[1000005];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        cha[i]=a[i]-a[i-1];
    }
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        if(cha[i]>0) cnt+=cha[i];
    }
    cout<<cnt;
    return 0;
}