洛谷 P5019 铺设道路 & [NOIP2018提高组]（贪心）

题目链接

https://www.luogu.org/problem/P5019

解题思路

一道典型的贪心题。

假设从左往右填坑，如果第i个深与第i+1个，那么第i+1个就不需要额外填；

如果第i+1个大于第i个，就需要填i+1-i的深度，所以就相当于把>0的差分数组加起来就AC了。

AC代码

 #include<iostream>

 #include<cstdio>

 using namespace std;

 int a[];

 long long ans;

 int main(){

     int n;

     cin>>n;

     for(int i=;i<=n;i++){

         scanf("%d",&a[i]);

         if(a[i]>a[i-]){

             ans+=a[i]-a[i-];

         }

     }

     cout<<ans;

     return ;

 }

//NOIP2018提高组Day1 t1