题解：AT_joi2021ho_a とてもたのしい家庭菜園 (Growing Vegetables is Fun 4)
_QWQ__QWQ_
·
·
题解
分析题意：
题意就是让前半段序列呈上升趋势，后半段呈下降趋势。
解题方法：
考虑差分出序列的高度。
$ 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;
}
```