题解：AT_joi2021ho_a とてもたのしい家庭菜園 (Growing Vegetables is Fun 4)

分析题意：

题意就是让前半段序列呈上升趋势，后半段呈下降趋势。

解题方法：

考虑差分出序列的高度。

x_i

表示以

i

为

k

的前半段需增加量。

y_i

表示以

i-1

为

k

的后半段需增加量。

从 $2$ 开始枚举：

如果当前

d_i

为负数，说明它比前一个小，为了满足前半段呈上升趋势，需要增加

x_i

。

从最后开始枚举：

如果当前

d_i

为正数，说明它比前一个大，为了满足后半段呈下降趋势，

y_i

增加。

注意：十年 OI 一场空，不开 long long 见祖宗。

附源码：

CPP

#include<bits/stdc++.h>
using namespace std;
const int maxn=200100;
long long n,sum=LONG_LONG_MAX-1,a[maxn],d[maxn],x[maxn],y[maxn];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		d[i]=a[i]-a[i-1];//求差分数组
	}
	for(int i=2;i<=n;i++){//从2枚举
		x[i]=x[i-1];
	    if(d[i]<=0){//如果为负数或0
	        x[i]+=-d[i]+1; //x[i]增加
	    }
	}
	for(int i=n;i>0;i--){//从最后面枚举
		y[i]=y[i+1];
	    if(d[i]>=0){//如果为整数或0
	        y[i]+=d[i]+1; //y[i]增加
	    }
	}
	for(int i=1;i<=n;i++){
	    sum=min(sum,max(x[i],y[i+1])); //最后答案取min(x[i],y[i+1])
	}
	cout<<sum;
	return 0;
}

题解：AT_joi2021ho_a とてもたのしい家庭菜園 (Growing Vegetables is Fun 4)

文章操作

分析题意：

解题方法：

从 $2$ 开始枚举：

从最后开始枚举：

附源码：

相关推荐

评论

题解：AT_joi2021ho_a とてもたのしい家庭菜園 (Growing Vegetables is Fun 4)

文章操作

分析题意：

解题方法：

从 222 开始枚举：

从最后开始枚举：

附源码：

相关推荐

评论

从 $2$ 开始枚举：