小美的陡峭值操作

[题目链接](https://www.nowcoder.com/practice/a4d34a7d8fb145af85f7190ee91dddf3)

思路

定义数组的陡峭值为相邻元素之差的绝对值之和： $\sum_{i=1}^{n-1} |a_{i+1} - a_i|$ 。可以最多进行一次操作：选一个区间 $[l, r]$ ，将区间内所有元素加 1。求操作后陡峭值的最小值。

操作对差分的影响

设差分 $d_i = a_{i+1} - a_i$ ，则陡峭值 $= \sum |d_i|$ 。

对区间 $[l, r]$ 整体加 1，只影响区间边界处的两个差分值：

若 $l > 1$ ： $d_{l-1}$ 增加 1（左边界外侧和内侧的差距变大）
若 $r < n$ ： $d_r$ 减少 1（右边界内侧和外侧的差距变小）

区间内部的差分完全不变。因此问题转化为：选两个位置 $i < j$ （分别对应 $l-1$ 和 $r$ ），使得 $|d_i + 1| + |d_j - 1|$ 相比 $|d_i| + |d_j|$ 的减少量最大。也可以只用一侧边界（ $l = 1$ 或 $r = n$ ）。

贪心扫描

定义两个收益函数：

左边界收益： $\text{lg}(i) = |d_i| - |d_i + 1|$ ，表示将 $d_i$ 加 1 后绝对值减少了多少
右边界收益： $\text{rg}(i) = |d_i| - |d_i - 1|$ ，表示将 $d_i$ 减 1 后绝对值减少了多少

最大总收益为以下四种情况的最大值：

不操作：收益 0
只用右边界（ $l = 1$ ）： $\max_j \text{rg}(j)$
只用左边界（ $r = n$ ）： $\max_i \text{lg}(i)$
同时用两侧（ $i < j$ ）： $\max_{i < j} [\text{lg}(i) + \text{rg}(j)]$

对于情况 4，从左到右扫描时维护 $\text{lg}$ 的前缀最大值，即可在 $O(n)$ 时间内求解。

样例演示

样例 1： $a = [1, 4, 2, 3, 4]$ ，差分 $d = [3, -2, 1, 1]$ ，初始陡峭值 $= 7$ 。

$\text{lg} = [-1, 1, -1, -1]$ ， $\text{rg} = [1, -1, 1, 1]$ 。

取 $i = 2, j = 3$ （即操作区间 $[3, 3]$ ）：收益 $= 1 + 1 = 2$ 。陡峭值 $= 7 - 2 = 5$ 。

样例 2： $a = [1, 2, 1]$ ，差分 $d = [1, -1]$ ，初始陡峭值 $= 2$ 。

$\text{lg} = [-1, 1]$ ， $\text{rg} = [1, -1]$ 。

只用右边界 $j = 1$ （即操作 $[1, 1]$ ）：收益 $= 1$ 。陡峭值 $= 2 - 1 = 1$ 。

复杂度分析

时间复杂度： $O(n)$ ，单次扫描差分数组。
空间复杂度： $O(n)$ ，存储差分数组。

代码

C++
Java

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

int main(){
    int T;
    scanf("%d", &T);
    while(T--){
        int n;
        scanf("%d", &n);
        vector<long long> a(n);
        for(int i = 0; i < n; i++) scanf("%lld", &a[i]);
        if(n == 1){
            printf("0\n");
            continue;
        }
        vector<long long> d(n - 1);
        long long base = 0;
        for(int i = 0; i < n - 1; i++){
            d[i] = a[i + 1] - a[i];
            base += abs(d[i]);
        }
        long long best = 0;
        long long maxLeft = LLONG_MIN;
        for(int i = 0; i < n - 1; i++){
            long long rg = abs(d[i]) - abs(d[i] - 1);
            if(maxLeft != LLONG_MIN){
                best = max(best, maxLeft + rg);
            }
            best = max(best, rg);
            long long lg = abs(d[i]) - abs(d[i] + 1);
            best = max(best, lg);
            maxLeft = max(maxLeft, lg);
        }
        printf("%lld\n", base - best);
    }
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine().trim());
        StringBuilder sb = new StringBuilder();
        while (T-- > 0) {
            int n = Integer.parseInt(br.readLine().trim());
            StringTokenizer st = new StringTokenizer(br.readLine().trim());
            long[] a = new long[n];
            for (int i = 0; i < n; i++) a[i] = Long.parseLong(st.nextToken());
            if (n == 1) {
                sb.append(0).append('\n');
                continue;
            }
            long[] d = new long[n - 1];
            long base = 0;
            for (int i = 0; i < n - 1; i++) {
                d[i] = a[i + 1] - a[i];
                base += Math.abs(d[i]);
            }
            long best = 0;
            long maxLeft = Long.MIN_VALUE;
            for (int i = 0; i < n - 1; i++) {
                long rg = Math.abs(d[i]) - Math.abs(d[i] - 1);
                if (maxLeft != Long.MIN_VALUE) {
                    best = Math.max(best, maxLeft + rg);
                }
                best = Math.max(best, rg);
                long lg = Math.abs(d[i]) - Math.abs(d[i] + 1);
                best = Math.max(best, lg);
                maxLeft = Math.max(maxLeft, lg);
            }
            sb.append(base - best).append('\n');
        }
        System.out.print(sb);
    }
}