这篇文章上次修改于 395 天前,可能其部分内容已经发生变化,如有疑问可询问作者。
本文共 847 个字,阅读时长 ≈ 3 分钟
提供一个比较抽象的讲解。
局部最大值可以抽象理解为一个山峰,我们要做的就是将一个山峰变为一个坡或者是平地。
刚开始我的思路是从左到右遍历,遇到一个山峰就把它削掉,削成它两边的数中最大的数。但是交了一发之后,我意识到这并不是最优解(那么多WA怎么可能是最优解啊喂)。这时我看到了样例四中的第二、三、四个数
发现在这种两面包夹芝士两山峰夹峡谷的情况中,把峡谷填高是比两个山峰削平更优的,因为把峡谷填高只需要一个操作,而把两个山峰削平需要两个操作。那要把峡谷填到什么高度呢?显然是两边的山峰中更高的那个。这里来浅浅证明一下。
如果把峡谷填到更矮的高度的话,很显然,第四个数的山峰还是一个山峰,并没有被消除。而要是填到更高的高度的话,两个山峰都会被消除,就会成为一个坡型和一个平地型。
最后,从第二个数遍历到倒数第二个数就行,一是防止数组越界,二是第一个数和最后一个数肯定不是山峰,所以不需要遍历。
代码:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#ifdef ONLINE_JUDGE
#define debug(x)
#else
#define debug(x) cout<<' '<<#x<<'='<<x<<endl;
#endif //调试用
using namespace std;
int t,n,ans;
int a[200005];
int main()
{
cin>>t;
while(t--){
cin>>n;
for(int i=1;i<=n;++i) cin>>a[i];
ans=0;
for(int i=2;i<n;++i){
if(a[i]>a[i-1]&&a[i]>a[i+1]){ //如果是一个山峰
a[i+1]=max(a[i],a[i+2]); //就把山峰后面的加高
ans++;//操作加一
}
}
cout<<ans<<endl;
for(int i=1;i<=n;++i) cout<<a[i]<<' ';
cout<<endl;
}
return 0;
}
没有评论