题目内容:

image-20210314191701464

题目分析:

看这道题的描述,可以看出应该是可以用贪心做的。

每个样例给定的总下限深度是确定的,而要在尽可能短的时间内填平,那就要使每次填平的数值越大越好,就是每次选择的[L,R]区间越大越好。

使[L,R]区间尽可能的大,那么就是以L开始能选择的越多越好,而可以选择的前提是下限深度不为0。

假设样例为3 3 3,那么以第一个开始选择的话,第二个跟第三个可以一起选择,总的花费就是三次。而如果样例是3,2,1的话,从第一个开始选择,第一次选择时,第二个,第三个可以一起选择,消耗一次,变为2,1,0。第二次选择,可以选择第一个第二个,消耗一次,变为1,0,0,第三次只用选择第一个,消耗一次,完成。

可以看出,如果后面一个的下陷深度如果小于前面一个的深度,那在从前面一个开始选择区间时,一定可以包含后面一个,就是后面一个跟随前面一个一起填平,不需要额外的消费,这个规则可以扩充至整个数列。

而如果后面一个的下陷深度大于前面一个(假设深度为n),就是说后面一个在不消耗额外次数的情况下只能跟随前面一个一起填平深度n,填平n后,它的前一个就变为0了,后面一个未填平的深度就需要从它自身开始选择,并额外消耗次数,当然从这个数开始选择的区间依然遵从这两个规则。

看题目中给的样例,(4,3,2,5,3,5)。从4开始分析,4大于前一个(默认0),需要消耗4-0次;3小于前面的4,可以跟随前一个填平,不需要消耗额外的次数;2小于前面的3,不需要消耗额外次数;5大于前面的2,当2经过两次变为0后,5无法再跟随前一个一起填平,所以需要额外消耗5-2=3次;3比前面的5小,不需要额外的次数;最后一个5,同理,前面的3变为0后,5无法跟随前面的一起填平,需要额外消耗5-3=2次。最终总共消耗,4+3+2=9次。

下面看具体AC代码:

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
using namespace std;
int num[100005]={0};

int main() {
int n,sum=0;
cin>>n;
for (int i = 1; i <= n; ++i) {
cin>>num[i];
}
for(int i=1;i<=n;i++){
if(num[i]>num[i-1])
sum+=num[i]-num[i-1];
}
cout<<sum<<endl;
return 0;
}