本蒟蒻刚A了这道黄题，特来发篇题解巩固一下。
Part 1:审题:春春是一名道路工程师，他要铺长度为n的道路，但整段道路有下陷，一开始，第 i 块区域下陷的深度为 d[i] 。他每天可以可以选择一段连续区间 [L,R] ，填充这段区间中的每块区域，让其下陷深度减少 1。输出使整段道路的下陷深度都变为 0 的最小时间。很多人看第一眼就知道是贪心，但贪心策略却不知道，别急，我们慢慢讲。
Part 2: 思路:1.既然知道这题是一道贪心，那我们先求出他的贪心思路，先画个图。
————1————2————3————4————5————6—————————————————— 地面
| | | | | | 凹陷程度
| | | | | |
| | | | |
| | |
| |
很直观了吧
2.画出来图，事情就变得简单了，我们先看1和2，可见，2比1的凹陷程度小，又因为春春可以选择[L,R]，为了填平1和2，他完全可以选择[1,2]区间，而二被填平时，1还没被填平，本来就要花4天才可以填平1，将区间变为[1,2],2被1连带着填平了，没花费别的天数，可见，当a[i]<a[i-1]时，根本不需要计算填平a[i]的天数。
3.那如果a[i]>a[i-1]呢,那不就是上面那种情况反过来吗,填完a[i-1]不用花费天数,那a[i]还剩a[i]-a[i-1]没填,这就要加到ans里面了,这就是我们的贪心策略。
4.代码就很简单了。
#include <bits/stdc++.h>
using namespace std;
int a[1000010];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
int ans=0;
for(int i=2;i<=n;i++)
{
if(a[i]>a[i-1])//小心下表越界
{
ans+=a[i]-a[i-1];
}
}
cout<<a[1]+ans//a[1]还没填<<endl;
return 0;
}
有问题可在评论区讨论。
