题解 【JOI 2021 Final】 とてもたのしい家庭菜園 4
LZH_LOVE_ZRG
·
·
题解
分析题面可知，这是一道序列操作题。
因为 A 数组前半段严格递增，后半段严格递减，
且只有加法一种操作，
所以我们可以使用差分思想。
记 B 为 A 的差分数组，我们接下来就用 B 进行一系列操作。
显而易见，这道题我们需要枚举界点，因此我们要定义：
那么可知： ans \gets \min\limits _{1\le i\le n}\{{\max(x_i,y_{i+1})}\}。
接下来的问题是，如何处理 x 与 y？
显而易见每次的 x 都是一个前缀的形式，而 y 是一个后缀的形式。
1. $b_i\le0$，即对答案有贡献（需要加才能符合严格递增），$x_i\gets x_{i-1}+\left\vert b_i\right\vert+1$；
2. $b_i>0$，即对答案没有贡献，$x_i\gets x_{i-1}$。
$y_i$ 同理，这里就不赘述了。
代码：
```
#include<bits/stdc++.h>
using namespace std;
const int N=200010;
int a[N],b[N];
long long x[N],y[N];
int main(){
int n; cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
b[i]=a[i]-a[i-1];
}
for(int i=2,j=n;i<=n;i++,j--){
x[i]=(b[i]<=0?x[i-1]-(b[i]-1):x[i-1]);
y[j]=(b[j]>=0?y[j+1]+(b[j]+1):y[j+1]);
}
long long ans=LONG_LONG_MAX;
for(int i=1;i<=n;i++)
ans=min(ans,max(x[i],y[i+1]));
cout<<ans;
return 0;
}
```