题解

题目描述

给定长度为 $n$ 的整型数组 $\{a_i\}_{i=1}^n$，定义数组的“陡峭值”为

现在允许对数组最多进行一次操作：选择一个区间 $[l,r]$，将区间内所有元素加 $1$。
问：在进行该操作（也可以不操作）的情况下，数组的陡峭值最小是多少？

思路

1. 初始陡峭值
   计算不做任何操作时的陡峭值
   $S$ = $sum_{i=2}^n |d_i|$,$d_i$ = $a_i$ - $a_{i-1}$

2. 操作影响分析
   若对区间 $[l,r]$ 全部加 $1$，则只有与区间边界相邻的两条差分可能变化：

   • 边界左侧：位置 $i=l$ 时，原来贡献 $|a_l - a_{l-1}|$ 变为 $|a_l+1 - a_{l-1}|$；
   • 边界右侧：位置 $i=r+1$ （若 $r<n$）时，原来贡献 $|a_{r+1} - a_r|$ 变为 $|a_{r+1} - (a_r+1)|$。

   记
   
   表示“左边界加 $1$”带来的陡峭值减少量；
   
   表示“右边界加 $1$”带来的陡峭值减少量。

   则对区间 $[l,r]$ 的总减少量为

   $$\Delta(l,r) = g_l + h_r\,.$$

   我们要选取 $l\le r$ 使得 $\Delta(l,r)$ 最大，从而使最终陡峭值
   
   最小。

3. “一次扫描”求最优

   • 预先计算 $g_i$ 和 $h_i$ 数组，时间 $O(n)$；
   • 维护前缀最大值$$\mathrm{prefMax}_i = \max_{1\le j\le i} g_j\,,$$ 然后枚举 $r=1\ldots n$，对于每个 $r$，最优的 $l\le r$ 时的减少量为$$\mathrm{prefMax}_r + h_r\,.$$
   • 在枚举过程中取最大即可，整体仍是 $O(n)$。

cpp

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

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

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<long long> a(n+2);
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }

        // 计算初始陡峭值 S
        long long S = 0;
        for (int i = 2; i <= n; i++) {
            S += llabs(a[i] - a[i-1]);
        }

        // 辅助数组 g 和 h
        vector<long long> g(n+1, 0), h(n+2, 0);
        // g[i] = |a[i]-a[i-1]| - |a[i]+1 - a[i-1]|
        for (int i = 2; i <= n; i++) {
            long long oldv = llabs(a[i] - a[i-1]);
            long long newv = llabs((a[i] + 1) - a[i-1]);
            g[i] = oldv - newv;
        }
        // h[i] = |a[i+1]-a[i]| - |a[i+1] - (a[i]+1)|
        for (int i = 1; i < n; i++) {
            long long oldv = llabs(a[i+1] - a[i]);
            long long newv = llabs(a[i+1] - (a[i] + 1));
            h[i] = oldv - newv;
        }

        // 前缀最大 g
        vector<long long> prefMax(n+1, LLONG_MIN);
        prefMax[1] = g[1];  // g[1] = 0
        for (int i = 2; i <= n; i++) {
            prefMax[i] = max(prefMax[i-1], g[i]);
        }

        // 枚举 r，寻找最大减少量
        long long bestGain = 0;
        for (int r = 1; r <= n; r++) {
            // prefMax[r] + h[r]
            bestGain = max(bestGain, prefMax[r] + h[r]);
        }

        // 答案 = S - bestGain
        cout << (S - bestGain) << "\n";
    }
    return 0;
}

python

# Python3 版本
import sys
input = sys.stdin.readline

def solve():
    t = int(input())
    for _ in range(t):
        n = int(input())
        a = list(map(int, input().split()))
        # 初始陡峭值
        S = sum(abs(a[i] - a[i-1]) for i in range(1, n))
        # 计算 g, h
        g = [0]*n
        h = [0]*n
        # g[i]: 左边界减少
        for i in range(1, n):
            old = abs(a[i] - a[i-1])
            new = abs(a[i] + 1 - a[i-1])
            g[i] = old - new
        # h[i]: 右边界减少
        for i in range(n-1):
            old = abs(a[i+1] - a[i])
            new = abs(a[i+1] - (a[i] + 1))
            h[i] = old - new
        # 前缀最大 g
        pref = [0]*n
        pref[0] = g[0]
        for i in range(1, n):
            pref[i] = max(pref[i-1], g[i])
        # 枚举 r 寻最优
        best = 0
        for r in range(n):
            best = max(best, pref[r] + h[r])
        print(S - best)

if __name__ == "__main__":
    solve()

Java

// Java 版本
import java.io.*;
import java.util.*;

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

            // 计算初始陡峭值
            long S = 0;
            for (int i = 2; i <= n; i++) {
                S += Math.abs(a[i] - a[i-1]);
            }

            // 计算 g 和 h 数组
            long[] g = new long[n+1];
            long[] h = new long[n+2];
            // 左边界
            for (int i = 2; i <= n; i++) {
                long oldv = Math.abs(a[i] - a[i-1]);
                long newv = Math.abs((a[i] + 1) - a[i-1]);
                g[i] = oldv - newv;
            }
            // 右边界
            for (int i = 1; i < n; i++) {
                long oldv = Math.abs(a[i+1] - a[i]);
                long newv = Math.abs(a[i+1] - (a[i] + 1));
                h[i] = oldv - newv;
            }

            // 前缀最大 g
            long[] prefMax = new long[n+1];
            prefMax[1] = g[1];
            for (int i = 2; i <= n; i++) {
                prefMax[i] = Math.max(prefMax[i-1], g[i]);
            }

            // 枚举 r 找最优
            long bestGain = 0;
            for (int r = 1; r <= n; r++) {
                bestGain = Math.max(bestGain, prefMax[r] + h[r]);
            }

            // 输出结果
            System.out.println(S - bestGain);
        }
    }
}

题目内容

定义一个数组的的陡峭值为:相邻两个元素之差的绝对值之和。

现在小美拿到了一个数组，她可以最多进行$1$次操作:选择一个区间，使得区间内所有元素加$1$。

小美希望最终数组的陡峭值尽可能小，你能帮帮她吗?

输入描述

第一行输入一个正整数$t$，代表询问次数。

对于每次询问输入两行:

第一行输入一个正整数$n$，代表数组长度。

第二行输入$n$个正整数$a_i$，代表小美拿到的数组。

$1≤t≤1000$

$2≤n≤10^5$

$1≤a_i≤10^9$

保证所有询问的$n$,的总和不超过$10^5$

输出描述

输出$t$行，输出一个整数，代表该次查询陡峭值的最小值。

样例1

输入

2
5
1 4 2 3 4
3 
1 2 1

输出

5
1

说明

第一组询问，选择$[3,4]$区间即可，数组变成{$1,4,3,4,4$}。

第二组询问，选择$[1,1]$区间即可，数组变成{$2,2,1$}。