这篇文章上次修改于 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;
}