[cf] 803 div2 B. Rising Sand

前言

t a g : tag : tag: 思维 区间修改 答案固定 传送门 :

题意

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

思路

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

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

分析一下 :

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

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

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

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

Mycode

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