自动搬运

查看原文

来自洛谷，原作者为

	LZH_LOVE_ZRG **

搬运于2025-08-24 22:29:31，当前版本为作者最后更新于2021-04-27 12:58:56，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

分析题面可知，这是一道序列操作题。

因为 $A$ 数组前半段严格递增，后半段严格递减，

且只有加法一种操作，

所以我们可以使用差分思想。

记 $B$ 为 $A$ 的差分数组，我们接下来就用 $B$ 进行一系列操作。

显而易见，这道题我们需要枚举界点，因此我们要定义：

• $x$ 数组，$x_i$ 表示从 $1$ ~ $i$ 严格递增所需的步数；
• $y$ 数组，$y_i$ 表示从 $i+1$ ~ $n$ 严格递减所需的步数。

那么可知： $ans \gets \min\limits _{1\le i\le n}\{{\max(x_i,y_{i+1})}\}$。

接下来的问题是，如何处理 $x$ 与 $y$？

显而易见每次的 $x$ 都是一个前缀的形式，而 $y$ 是一个后缀的形式。

$x_i$ 的赋值有 $2$ 种情况：

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