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

Anye
Anye
发布于 2019-09-03 / 6 阅读
0
0

【百题千解】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;
}


评论