(greedy) B. avoid local maximums

B. Avoid Local Maximums

lianjie
The question ：

If I found $a[i]>a[i-1]$&&$a[i]>a[i+1]$ We need to make some changes when , So that the entire sequence does not exist $a[i]>a[i-1]$&&$a[i]>a[i+1]$, Find the minimum number of operations .

Ideas ：

The problem of greed must be that the more impact the current operation has, the better

1. The idea is to traverse from left to right , If I found $a[i]>a[i-1]$&&$a[i]>a[i+1]$ When , modify $a[i]=a[i-1]$, But this is obviously not optimal , Because if you modify it like this , The impact result is only ：$a[i],a[i-1],a[i+1]$ The three numbers are in harmony , But it has no effect on other numbers . So we don't consider modifying $a[i]$.
2. Do not modify $a[i-1]$, Because it will affect the previous numbers
3. At last we decided to revise $a[i+1]$, because $a[i+1]$ Would be right $a[i]$ and $a[i+2]$ All have an impact , If you just let $a[i+1]=a[i]$, There may be a[i+2] Still more than $a[i+1]anda[i+3]$ The big picture , So let $a[i+1]=max(a[i],a[i+2])$ It can also affect $a[i+2]$.
   such as ：

1 2 1 3 2 

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 2e5+100;
int b[N],a[N];
int n;
int main()
{
    
	int t;
	cin>>t;
	while(t--)
	{
    
		cin>>n;
		for(int i=0;i<n;i++) cin>>a[i];
		
		int cnt=0;
		for(int i=1;i<n-1;i++)
		{
    
			if(a[i]>a[i-1]&&a[i]>a[i+1])
			a[i+1]=max(a[i],a[i+2]),cnt++;
		}
		
		cout<<cnt<<endl;
		
		for(int i=0;i<n;i++) cout<<a[i]<<" ";
		cout<<endl;
	}
    return 0;
}