算法思路

要把序列变为先严格递增后严格递减的单峰序列，只能对任意位置做“+1”操作，且操作次数要最少。可以分三步：

前缀严格递增预处理

令 b[j] 表示将原序列 a[1..j] 调整为严格递增时，第 j 个位置的最终值最小可能值；同时记录所需的操作次数前缀和 f[j]。 具体做法：

• 初始化 b[1] = a[1], f[1] = 0。

• 对于 j = 2..n：

  b[j] = max(a[j], b[j-1] + 1)
  f[j] = f[j-1] + (b[j] - a[j])
  

此时，f[j] 为把 a[1..j] 调整成严格递增的最小总操作数，且第 j 位多加了 inc[j] = b[j] - a[j] 次。

后缀严格递减预处理

同理，令 c[j] 表示将原序列 a[j..n] 调整为严格递减时，第 j 个位置的最终值最小可能值；记录所需操作次数后缀和 g[j]。

• 初始化 c[n] = a[n], g[n] = 0。

• 对于 j = n-1..1：

  c[j] = max(a[j], c[j+1] + 1)
  g[j] = g[j+1] + (c[j] - a[j])
  

此时，g[j] 为把 a[j..n] 调整成严格递减的最小总操作数，且第 j 位多加了 dec[j] = c[j] - a[j] 次。

枚举峰值位置

单峰位置 i 必须满足 2 ≤ i ≤ n-1。若选 i 为峰值，则左右两段分别使用上述预处理结果，但第 i 位的操作在左右都算过一次，需要减去一次多余的操作：

总操作 = f[i] + g[i] - min(inc[i], dec[i])

其中 inc[i] = b[i] - a[i]，dec[i] = c[i] - a[i]。 遍历 i，取最小值即为答案。

复杂度分析

• 时间复杂度：

  • 前缀预处理和后缀预处理各做一次线性扫描，O(n)
  • 枚举峰值位置一次线性扫描，O(n) 总计 O(n)。

• 空间复杂度： 需要存储常数个长度为 n 的数组，O(n)。

代码实现

Python

def solve():
    import sys
    data = sys.stdin.read().split()
    n = int(data[0])
    a = list(map(int, data[1:]))

    # 前缀预处理
    b = [0] * n
    f = [0] * n
    b[0] = a[0]
    for i in range(1, n):
        # 保证严格递增
        b[i] = max(a[i], b[i-1] + 1)
        f[i] = f[i-1] + (b[i] - a[i])

    # 后缀预处理
    c = [0] * n
    g = [0] * n
    c[n-1] = a[n-1]
    for i in range(n-2, -1, -1):
        # 保证严格递减
        c[i] = max(a[i], c[i+1] + 1)
        g[i] = g[i+1] + (c[i] - a[i])

    # 枚举峰值
    ans = 10**30
    for i in range(1, n-1):
        inc = b[i] - a[i]
        dec = c[i] - a[i]
        total = f[i] + g[i] - min(inc, dec)
        if total < ans:
            ans = total

    print(ans)

if __name__ == "__main__":
    solve()

Java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(in.readLine());
        long[] a = new long[n];
        StringTokenizer st = new StringTokenizer(in.readLine());
        for (int i = 0; i < n; i++) {
            a[i] = Long.parseLong(st.nextToken());
        }

        // 前缀预处理
        long[] b = new long[n], f = new long[n];
        b[0] = a[0];
        for (int i = 1; i < n; i++) {
            b[i] = Math.max(a[i], b[i-1] + 1);
            f[i] = f[i-1] + (b[i] - a[i]);
        }

        // 后缀预处理
        long[] c = new long[n], g = new long[n];
        c[n-1] = a[n-1];
        for (int i = n-2; i >= 0; i--) {
            c[i] = Math.max(a[i], c[i+1] + 1);
            g[i] = g[i+1] + (c[i] - a[i]);
        }

        // 枚举峰值位置
        long ans = Long.MAX_VALUE;
        for (int i = 1; i < n-1; i++) {
            long inc = b[i] - a[i];
            long dec = c[i] - a[i];
            long total = f[i] + g[i] - Math.min(inc, dec);
            if (total < ans) ans = total;
        }

        System.out.println(ans);
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    // 前缀预处理
    vector<long long> b(n), f(n);
    b[0] = a[0];
    for (int i = 1; i < n; i++) {
        b[i] = max(a[i], b[i-1] + 1);
        f[i] = f[i-1] + (b[i] - a[i]);
    }

    // 后缀预处理
    vector<long long> c(n), g(n);
    c[n-1] = a[n-1];
    for (int i = n-2; i >= 0; i--) {
        c[i] = max(a[i], c[i+1] + 1);
        g[i] = g[i+1] + (c[i] - a[i]);
    }

    // 枚举峰值位置
    long long ans = LLONG_MAX;
    for (int i = 1; i < n-1; i++) {
        long long inc = b[i] - a[i];
        long long dec = c[i] - a[i];
        long long total = f[i] + g[i] - min(inc, dec);
        ans = min(ans, total);
    }

    cout << ans << "\n";
    return 0;
}

题目内容

多多在纸上写下了一个整数序列，他可以对任意一个数进行 $+1$ 操作，每个数的操作次数不限。

他想知道，他至少要操作多少次，可以使这个序列变成一个单峰序列。

单峰序列定义：假设序列为 $a_1,a_2,...,a_n$ ，存在一个数 $i (1 < i < n )$ ，满足 $a_1 < a_2 < a_3 … < a_i >a_{i+1}>a_{i+2}>…>a_n$ ，即这个序列先严格递增再严格递减。

输入描述

输入为两行，第一行为一个整数 $n(3≤n≤100000)$ ，表示序列长度。

第二行为 $n$ 个整数，表示序列中的数。$(1<=a_i<=10000000)$

输出描述

输出最小的操作次数

样例1

输入

3
2 2 2

输出

1