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

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

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

首先来分析示例数据 1 这是按照示例数据画出来的示意图, 那么填过之后就变成了这样2 这样太麻烦了,仔细观察图2,有没有发现一个规律,

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

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

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

继续 6

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

最后 7

我们的算法应该这样实现

123]

至此这道题就算完成了!


最后贴上完整代码

#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;
}


评论