NOIP提高组2018试题解析 Day1 T1 铺设道路 P5019

题目描述

春春是一名道路工程师,负责铺设一条长度为 nn 的道路。

铺设道路的主要工作是填平下陷的地表。整段道路可以看作是 nn 块首尾相连的区域,一开始,第 ii 块区域下陷的深度为 d_idi​ 。

春春每天可以选择一段连续区间[L,R][L,R] ,填充这段区间中的每块区域,让其下陷深度减少 11。在选择区间时,需要保证,区间内的每块区域在填充前下陷深度均不为 00 。

春春希望你能帮他设计一种方案,可以在最短的时间内将整段道路的下陷深度都变为 00 。

输入格式

输入文件包含两行,第一行包含一个整数 nn,表示道路的长度。 第二行包含 nn 个整数,相邻两数间用一个空格隔开,第ii 个整数为 d_idi​ 。

输出格式

输出文件仅包含一个整数,即最少需要多少天才能完成任务。

输入输出样例

输入 #1复制
6
4 3 2 5 3 5
输出 #1复制
9

说明/提示

【样例解释】

一种可行的最佳方案是,依次选择: [1,6][1,6]、[1,6][1,6]、[1,2][1,2]、[1,1][1,1]、[4,6][4,6]、[4,4][4,4]、[4,4][4,4]、[6,6][6,6]、[6,6][6,6]。

【数据规模与约定】

对于 30\%30% 的数据,1 ≤ n ≤ 101≤n≤10 ;
对于 70\%70% 的数据,1 ≤ n ≤ 10001≤n≤1000 ;
对于 100\%100% 的数据,1 ≤ n ≤ 100000 , 0 ≤ d_i ≤ 100001≤n≤100000,0≤di​≤10000 。

 
 
这一道题我看到以后的第一感觉是 仿佛应该是非常的简单 又仿佛是非常的难
根据我的印象  我之前做过类似的题目
我记得是这个样子
原数列为432535    那么这个数列中每相邻的两个数之间的和累计起来 就是1+1+3+2+2=9  事情真的有这么巧吗?我都难以置信诶
 
我们再来举一个例子试一下 
123456   1+1+1+1+1=5完了 沧桑去世  应该是6次才对
23471   1+1+3+6=11   也不对啊 应该是7次
 
停停停 一定是那个地方出错了
总是感觉 算一下差的和是一个正解
 
算了 我们还是来正八经儿第证明一下看一看吧
 
比如现在有两个坑紧挨着小坑在前 大坑在后
大坑深度为5  小坑的深度为2   那么肯定这个时候的决策时一起减1   那么只要5减去3   2也就跟着5一起消失了
也就是说!!!!!
而我们从前往后进行枚举  如果a[i]>a[i-1] 那么就设一个sum累加器    sum+=a[i]-a[i-1]
然后a[1]-a[0]也并不妨碍 a[0]正好是0嘛
 
 
那么我们如果这样子进行处理的话
就相当于用了一个贪心的算法
 
就相当于 我们来计算每一个坑会对答案多带来多大的贡献
那么怎样子来验证这个贪心算法的正确性呢?
很简单 找几个例子带入算一算就可以发现是对的了     
我们还是拿本题的样例再来理解一下吧
4 3 2 5 3 5
(猫咪表示 你怎么还没讲完!
sum一开始的值是0
首先我们先看4   sum肯定是要加上一个4 - 0的   也就是说   肯定至少要经过4天才能把这个深度为4的坑给填掉  sum=4
再来看3 3比4小 就不进行操作 也就是说在把4覆盖完的过程中 3也就随之“免费”地填完了
2也是同样的情况  因为3<4 (猫咪表示 你这不是废话吗!   也就是说在3倍填完的同时2也被填了
再看5    这时出现了不一样的情况 5>2   所以sum要加上3  sum=7    也就是说2填完的时候 原本深度为5的那个坑 还有深度为3的没有填完 所以要再累加上3   在这个时候为什么和4没有关系了呢?   很显然 2早就变成0了  这时候4和5就隔开了
再看3  很显然不用管
再看最后的那个5   也就是说3填完的时候5还有2的深度没有填上 sum要再加上2  sum=9   两个5之间是没有关联的  因为当他们的深度都变成2的时候 3那个地方已经成了0了   他们是分隔开的 不能一起减2   要分别来考虑
 
 
这么理了一遍 感觉畅快多了   所以这个算法能理下来 它就是正确的了啦
 
 
非常开心!
期望得分:100   得分:100
代码如下:
那个unsigned long long 感觉没有非常大的必要  还是谨慎一点好啊
#include<bits/stdc++.h>
#define maxn 100005
using namespace std;
int arr[maxn];
int main()
{
int n;scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%d",&arr[i]);
unsigned long long ans=;
for(int i=;i<=n;i++)
//if(arr[i]>arr[i-1])
ans+=1ull*(arr[i]>arr[i-])*(arr[i]-arr[i-]);
printf("%llu",ans);
return ;
}
 
 
 
 
 
上一篇:JavaScript-语法基础


下一篇:luogu5019 [NOIp2018]铺设道路 (贪心)