【百题千解】A-道路铺设 题解（2018NOIP提高组复赛）

分析

首先来分析示例数据

这是按照示例数据画出来的示意图， 那么填过之后就变成了这样

这样太麻烦了，仔细观察图 2，有没有发现一个规律：

其实我们可以这样子： 先把第 1 列的道路先填起来，记到天数 sum 中，然后将第一列下陷的深度后面的深度相比较，若后面的有一个小于它，则整条道路上都被填满了最浅的那个坑的深度的土，如图。

然后我们通过使用 for 循环遍历整条道路，在前一步的基础上，增加天数 sum，如图

图片颜色标记错了，第5列的5也是红色

继续

图片颜色标记错了，第5列的5也是红色

最后

我们的算法应该这样实现

至此这道题就算完成了！

最后贴上完整代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    //freopen ("road.in","r",stdin);
    //freopen ("road.out","w",stdout);
    int n,sum=0,l=0;
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        {
            int a;
            scanf("%d",&a);
            if(a>l)
                sum+=(a-l);
            l=a;
        }
        printf("%d\n",sum);
    return 0;
}