题目描述】
给定一个长度为 $N$ 的序列 $A_i$。你可以进行若干次操作：

  • 选定一个区间 $[L, R]$，让这个区间里的数加 $1$。
    设经过若干次操作后的序列为 $B_i$，你需要让 $B_i$ 满足下述要求：
  • 存在一个整数 $k \in [1, N]$，满足对于子序列 $A_1 = {B_1, B_2, \dots, B_k}$ 为严格递增序列，对于子序列 $A_2 = {B_k, B_{k+1}, \dots, B_N}$ 为严格递减序列。
    你想知道最少需要多少次操作才能满足上述要求。
    【输入格式】
  • 第一行一个整数 $N$ 代表序列长度。
  • 第二行 $N$ 个整数 $A_i$ 代表序列。
    【输出格式】
  • 一行一个整数代表最小操作次数。
    【输入输出样例】
  1. 输入：5 / 3 2 2 3 1 $\rightarrow$ 输出：3
  2. 输入：5 / 9 7 5 3 1 $\rightarrow$ 输出：0
  3. 输入：2 / 2021 2021 $\rightarrow$ 输出：1
  4. 输入：8 / 12 2 34 85 4 91 29 85 $\rightarrow$ 输出：53

1. 核心思路：将单调性转化为正负号
题目要求序列 $B$ 满足：$B_1 < B_2 < \dots < B_k$（严格递增）且 $B_k > B_{k+1} > \dots > B_N$（严格递减）。
设差分数组 $C_i = A_i - A_{i-1}$：

  • 严格递增 $\implies C_i \ge 1$（对于 $i \in [2, k]$）。
  • 严格递减 $\implies C_i \le -1$（对于 $i \in [k+1, N]$）。
    2. 核心技巧：区间修改的双重收益
    一次区间加法操作 $[L, R]$ 会使差分数组发生如下变化：$C_L \gets C_L + 1$，$C_{R+1} \gets C_{R+1} - 1$。
  • 这意味着我们可以同时修复左侧一个需要变大的 $C_L$ 和右侧一个需要变小的 $C_{R+1}$。
  • 如果我们只需要修改一侧，只需让另一侧的修改点落在数组范围外（即 $R+1 = N+1$ 或 $L=1$）。
    3. 解题步骤：前后缀分解
  • 左侧代价 $F[i]$：使前 $i$ 个数严格递增所需增加的总量：$F[i] = F[i-1] + \max(0LL, 1 - C_i)$。
  • 右侧代价 $Z[i]$：使从 $i$ 到 $N$ 严格递减所需减少的总量：$Z[i] = Z[i+1] + \max(0LL, C_i + 1)$。
  • 枚举山峰 $k$：由于一次操作可以同时满足两侧各一个单位的需求，总操作次数为 $\min_{1 \le k \le N} { \max(F[k], Z[k+1]) }$。
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
int main(){
    int N,themax=999999,thismax;
    cin>>N;
    vector<int>A(N+2,0);
    vector<int>C(N+2,0);
    vector<int>Z(N+2,0);
    vector<int>F(N+2,0);
    for(int i=1;i<=N;i++)
    cin>>A[i];
    C[1]=A[1];
    for(int i=2;i<=N;i++)
    C[i]=A[i]-A[i-1];
    for(int i=2;i<=N;i++)
    F[i]=F[i-1]+max(0,1-C[i]);
    for(int i=N;i>=2;i--)
    Z[i]=Z[i+1]+max(0,1+C[i]);
    for(int k=1;k<=N;k++)
    {
        thismax=max(F[k],Z[k+1]);
        if(thismax<themax)
        themax=thismax;
    }
    cout<<themax;
 
}