[cf] 803 div2 B. Rising Sand

前言

$tag:$思维区间修改答案固定
传送门 :

题意

给定一个数组$A$,对于$A[i]>A[i-1]+A[i+1]$,我们定义为过高,同时给定一个$k$,你可以让区间长度为$k$的$A[i]+1$,询问执行任意次操作止之后可以获得最大的过高的堆数

思路

因为答案的计算是$A[i]>A[i-1]+A[i+1]$

因此我们发现$k\ge 2$的时候,十分难改变或者十分难增加答案

分析一下 :

• 如果整个三元组增加 , $a_i+1>a_{i+1}+a_{i-1}+2$
• 如果是部分增加,$a_i+1>a_{i-1}+a_{i+1}+1$

因此可以看出不操作是最好的

而对于$k==1$的情况

我们可以知道因为是任意次操作,所以最多有$\frac{n-2}{2}$,不计算端点

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 ;
}