题解 | #小美的陡峭值操作#

题目链接

小美的陡峭值操作

题目描述

给定一个数组 $a$ ，其“陡峭值”定义为相邻元素之差的绝对值之和，即 $\sum_{i=1}^{n-1} |a_i - a_{i-1}|$ 。

我们最多可以执行一次操作：选择一个连续的子数组（区间） $[l, r]$ ，并将区间内的所有元素都加 1。

目标是找到一个最优的操作（或者不操作），使得最终数组的陡峭值尽可能小。

解题思路

这是一个最优化问题。一个朴素的想法是枚举所有可能的区间 $[l, r]$ ，对每个区间计算操作后的陡峭值，然后取最小值。但这样做的时间复杂度为 $O(n^3)$ 或 $O(n^2)$ ，无法通过本题的数据范围。我们需要一个更高效的方法。

分析操作的影响

关键在于分析“区间加一”这个操作如何改变总的陡峭值。设初始陡峭值为 $D = \sum_{i=1}^{n-1} |a_i - a_{i-1}|$ 。当我们对区间 $[l, r]$ 进行加一操作后，数组变为 $a'$ 。

区间内部：对于任意 $l < i \le r$ ，新的差值为 $|a'_i - a'_{i-1}| = |(a_i+1) - (a_{i-1}+1)| = |a_i - a_{i-1}|$ 。区间内部的差值项不变。
区间外部：对于 $i < l$ 或 $i > r+1$ 的项，也显然不变。

真正的变化只发生在区间的两个边界处：

左边界（如果 $l > 0$ ）：差值项从 $|a_l - a_{l-1}|$ 变为 $|(a_l+1) - a_{l-1}|$ 。
右边界（如果 $r < n-1$ ）：差值项从 $|a_{r+1} - a_r|$ 变为 $|a_{r+1} - (a_r+1)|$ 。

我们的目标是最小化最终的陡峭值，这等价于最大化这次操作带来的减少量（或称为“收益”）。总收益 Gain(l, r) = Gain_left(l) + Gain_right(r) 其中：

Gain_left(l) = |a_l - a_{l-1}| - |(a_l+1) - a_{l-1}| (当 $l>0$ 时，否则为 0)
Gain_right(r) = |a_{r+1} - a_r| - |a_{r+1} - (a_r+1)| (当 $r<n-1$ 时，否则为 0)

简化收益函数

我们可以通过简单的分类讨论来简化收益的计算：

对于 Gain_left(l):
- 如果 $a_l < a_{l-1}$ (下坡)，则 Gain_left(l) = (a_{l-1} - a_l) - (a_{l-1} - a_l - 1) = 2。
- 如果 $a_l \ge a_{l-1}$ (上坡或平坡)，则 Gain_left(l) 会是 0 或 -2。
对于 Gain_right(r):
- 如果 $a_{r+1} > a_r$ (上坡)，则 Gain_right(r) = (a_{r+1} - a_r) - (a_{r+1} - a_r - 1) = 2。
- 如果 $a_{r+1} \le a_r$ (下坡或平坡)，则 Gain_right(r) 会是 0 或 -2。

等等，这个简化好像有点问题。让我们重新分析 |x| - |x-1| 的变化。当 x 从 a-b 变为 a-(b+1)，即 x 减 1。函数 $f(x) = |x|$ 的导数在 $x>0$ 时为 1，在 $x<0$ 时为 -1。

Gain_left(l): |a_l - a_{l-1}| - |a_l - a_{l-1} + 1|
- 若 $a_l - a_{l-1} > 0$ (上坡)，收益为 $x - (x+1) = -1$ * 2 = -2. (错误，绝对值不这么算)

正确的简化：对任意两个数 $x, y$ ：

$|y - x| - |y - (x+1)|$ : 当 $x$ 增加 1。
- 若 $y > x$ : $|y-x| - |y-x-1|$ 。如果 $y-x \ge 1$ , 结果为 $(y-x)-(y-x-1)=1$ 。
- 若 $y \le x$ : $|x-y| - |x+1-y|$ 。如果 $x-y \ge 0$ , 结果为 $(x-y)-(x+1-y)=-1$ 。
Gain_left(l): $a_l$ 增加 1。
- 若 $a_{l-1} > a_l$ (下坡)，收益为 2. (例如 $|5-2| - |5-3| = 3-2=1$ )
- 若 $a_{l-1} \le a_l$ (上坡/平)，收益为 -2. (例如 $|2-5|-|-|2-6| = 3-4=-1$ )

$O(n)$ 求解

问题变成了寻找 $l, r$ ( $0 \le l \le r < n$ ) 来最大化 Gain_left(l) + Gain_right(r)。这可以被高效解决：

令 max_gain_right[i] 表示，如果我们选择的区间右端点 $r$ 在 $[i, n-1]$ 范围内，我们能获得的最大右边界收益。

$\text{max_gain_right}[i] = \max_{j=i}^{n-1} (\text{Gain_right}(j))$

这个数组可以从右到左遍历一次预计算出来。

$\text{max_gain_right}[i] = \max(\text{Gain_right}(i), \text{max_gain_right}[i+1])$

然后，我们遍历所有可能的左端点 $l$ (从 0 到 $n-1$ )，对于每个 $l$ ，它可以匹配的最好右端点 $r$ ( $r \ge l$ ) 已经记录在 max_gain_right[l] 中。

所以，我们只需要计算 $\max_{l=0}^{n-1} (\text{Gain_left}(l) + \text{max_gain_right}[l])$ 。

最终，我们能获得的总收益是这个最大值和 0 (不操作) 中的较大者。

最终算法

计算初始陡峭值 $D_{initial}$ 。
创建 gain_left 和 gain_right 两个大小为 $n$ 的数组。
遍历数组 $a$ 计算每个位置作为左/右端点时的收益，并填充数组。
- gain_left[0] = 0, gain_right[n-1] = 0。
- For $i=1 \dots n-1$ : gain_left[i] = |a[i]-a[i-1]| - |a[i]+1-a[i-1]|
- For $i=0 \dots n-2$ : gain_right[i] = |a[i+1]-a[i]| - |a[i+1]-(a[i]+1)|
创建 max_gain_right 数组，从右向左遍历计算后缀最大值。
遍历 $l$ 从 0 到 $n-1$ ，计算 gain_left[l] + max_gain_right[l]，找出最大值 max_total_gain。
最终答案为 $D_{initial} - \max(0, \text{max\_total\_gain})$ 。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <numeric>
#include <cmath>
#include <algorithm>

using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<long long> a(n);
    long long initial_steepness = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        if (i > 0) {
            initial_steepness += abs(a[i] - a[i - 1]);
        }
    }

    if (n <= 1) {
        cout << 0 << endl;
        return;
    }

    vector<long long> gain_left(n, 0), gain_right(n, 0);
    for (int i = 1; i < n; ++i) {
        gain_left[i] = abs(a[i] - a[i - 1]) - abs(a[i] + 1 - a[i - 1]);
    }
    for (int i = 0; i < n - 1; ++i) {
        gain_right[i] = abs(a[i + 1] - a[i]) - abs(a[i + 1] - (a[i] + 1));
    }

    vector<long long> max_gain_right(n, 0);
    max_gain_right[n - 1] = gain_right[n - 1];
    for (int i = n - 2; i >= 0; --i) {
        max_gain_right[i] = max(gain_right[i], max_gain_right[i + 1]);
    }

    long long max_total_gain = 0;
    for (int l = 0; l < n; ++l) {
        max_total_gain = max(max_total_gain, gain_left[l] + max_gain_right[l]);
    }

    cout << initial_steepness - max_total_gain << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

import java.util.Scanner;
import java.lang.Math;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            solve(sc);
        }
    }

    public static void solve(Scanner sc) {
        int n = sc.nextInt();
        long[] a = new long[n];
        long initialSteepness = 0;
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextLong();
            if (i > 0) {
                initialSteepness += Math.abs(a[i] - a[i - 1]);
            }
        }

        if (n <= 1) {
            System.out.println(0);
            return;
        }

        long[] gainLeft = new long[n];
        long[] gainRight = new long[n];

        for (int i = 1; i < n; i++) {
            gainLeft[i] = Math.abs(a[i] - a[i - 1]) - Math.abs(a[i] + 1 - a[i - 1]);
        }
        for (int i = 0; i < n - 1; i++) {
            gainRight[i] = Math.abs(a[i + 1] - a[i]) - Math.abs(a[i + 1] - (a[i] + 1));
        }
        
        long[] maxGainRight = new long[n];
        maxGainRight[n-1] = gainRight[n-1];
        for(int i = n - 2; i >= 0; i--) {
            maxGainRight[i] = Math.max(gainRight[i], maxGainRight[i+1]);
        }
        
        long maxTotalGain = 0;
        for (int l = 0; l < n; l++) {
            maxTotalGain = Math.max(maxTotalGain, gainLeft[l] + maxGainRight[l]);
        }

        System.out.println(initialSteepness - maxTotalGain);
    }
}

import sys

def solve():
    n = int(sys.stdin.readline())
    a = list(map(int, sys.stdin.readline().split()))
    
    initial_steepness = 0
    for i in range(1, n):
        initial_steepness += abs(a[i] - a[i-1])

    if n <= 1:
        print(0)
        return

    gain_left = [0] * n
    gain_right = [0] * n

    for i in range(1, n):
        gain_left[i] = abs(a[i] - a[i-1]) - abs(a[i] + 1 - a[i-1])
    for i in range(n - 1):
        gain_right[i] = abs(a[i+1] - a[i]) - abs(a[i+1] - (a[i] + 1))
        
    max_gain_right = [0] * n
    max_gain_right[n-1] = gain_right[n-1]
    for i in range(n - 2, -1, -1):
        max_gain_right[i] = max(gain_right[i], max_gain_right[i+1])
        
    max_total_gain = 0
    for l in range(n):
        max_total_gain = max(max_total_gain, gain_left[l] + max_gain_right[l])
        
    print(initial_steepness - max_total_gain)

def main():
    t = int(sys.stdin.readline())
    for _ in range(t):
        solve()

if __name__ == "__main__":
    main()

算法及复杂度

算法：动态规划 / 贪心
时间复杂度： $O(n)$ 。计算初始陡峭值、计算左右边界收益、计算右边界收益的后缀最大值、以及最后遍历寻找最大总收益，这四个步骤都是线性的。
空间复杂度： $O(n)$ 。需要额外的空间来存储收益数组和后缀最大值数组。