[cf] 803 div2 B. Rising Sand

Preface

$tag:$ thinking Interval modification Fixed answer
Portal :

The question

Given an array $A$, about $A[i]>A[i-1]+A[i+1]$, We define it as Too high , At the same time, give a $k$, You can make the interval length $k$ Of $A[i]+1$, inquiry After any operation You can get the maximum number of heaps that are too high

Ideas

Because the answer is calculated as $A[i]>A[i-1]+A[i+1]$

So we found that $k\ge 2$ When , Very difficult to change or add answers

Look at the :

• If the entire triple is increased , $a_i+1>a_{i+1}+a_{i-1}+2$
• In case of partial increase ,$a_i+1>a_{i-1}+a_{i+1}+1$

So we can see that No operation is the best

And for $k==1$ The situation of

We can know that because it is an arbitrary operation , So at most $\frac{n-2}{2}$, Do not calculate endpoints

Mycode

int n,k;
int a[N];
 
 
void solve(){
    
	cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>a[i];
	
	int cnt = 0 ;
	if(k!=1){
    
		for(int i= 2 ; i <n ; i ++ )
			if(a[i] > a[i-1] + a[i+1]) cnt++;
	}else{
    
		if(n&1) cnt = (n-2)/2 + 1;
		else cnt = (n-2)/2;
	}
	cout<<cnt<<endl;
	
	
}
 
int main(){
    
	int t;cin>>t;while(t--)
    solve();
    return 0 ;
}