思路:简单动态规划:前缀最值

一个显然的思路是枚举染色的断点，然后分别计算前缀和后缀的极差，相减取绝对值。这些答案里取最小即可。

由于n 比较大，我们需要提前算出前缀每个位置的极差，以及后缀每个位置的极差。

f1[i] 表示前i 个位置的极差，f2[i] 表示后i 个位置的极差。

f1[i] = max(max[i-1], a[i]) - min(min[i-1], a[i])

注意这里的max[i-1]和max[i-1]可以用一个变量维护，不需要开辟数组去存储。

同理:f2[i] = max(max[i+1], a[i]) - min(min[i+1], a[i])

然后枚举断点i，计算abs(f1[i] - f2[i+1])的最小值即可。

代码

cpp

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

int main(void) {
    // 输入数组大小
    int n;
    cin >> n;
    
    // 定义数组，存储输入的值
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    // 定义常量inf，用于初始化极差
    const int inf = 0x3f3f3f3f;
    
    // 定义前缀和后缀极差数组
    vector<int> f1(n + 1), f2(n + 1);
    
    // 初始化最大值和最小值
    int mx = -inf, mi = inf;

    // 计算前缀极差
    for (int i = 1; i <= n; i++) {
        mx = max(mx, a[i]); // 更新前缀最大值
        mi = min(mi, a[i]); // 更新前缀最小值
        f1[i] = mx - mi;    // 计算前i个位置的极差
    }

    // 重置最大值和最小值
    mx = -inf, mi = inf;

    // 计算后缀极差
    for (int i = n; i > 0; i--) {
        mx = max(mx, a[i]); // 更新后缀最大值
        mi = min(mi, a[i]); // 更新后缀最小值
        f2[i] = mx - mi;    // 计算后i个位置的极差
    }

    // 初始化答案为无限大
    int ans = inf;

    // 枚举断点i，计算最小的绝对差
    for (int i = 1; i < n; i++) {
        ans = min(ans, abs(f1[i] - f2[i + 1])); // 更新最小绝对差
    }
    
    // 输出最终结果
    cout << ans << endl;

    return 0;
}

java

def main():
    n = int(input())
    a = [0] + list(map(int, input().split()))

    inf = float('inf')
    
    f1 = [0] * (n + 1)
    f2 = [0] * (n + 1)
    
    mx = -inf
    mi = inf


    for i in range(1, n + 1):
        mx = max(mx, a[i])
        mi = min(mi, a[i])
        f1[i] = mx - mi


    mx = -inf
    mi = inf


    for i in range(n, 0, -1):
        mx = max(mx, a[i])
        mi = min(mi, a[i])
        f2[i] = mx - mi

    ans = inf

    for i in range(1, n):
        ans = min(ans, abs(f1[i] - f2[i + 1]))
    
    print(ans)

if __name__ == "__main__":
    main()

python

def get_min_value(data):
    reverse_min_value = [0] * len(data)
    min_val = 99999999
    max_val = -99999999
    for i in range(len(data)-1, -1, -1):
        val = data[i]
        min_val = min(min_val, val)
        max_val = max(max_val, val)
        reverse_min_value[i] = max_val - min_val

    result = 999999999
    min_val = 999999999
    max_val = -999999999
    for i in range(0, len(data) - 1):
        val = data[i]
        min_val = min(min_val, val)
        max_val = max(max_val, val)
        diff = max_val - min_val
        result_val = abs(diff - reverse_min_value[i+1])
        result = min(result_val, result)
    return result

_ = input()
data_list = [int(x) for x in input().split()]
print(get_min_value(data_list))

OJ会员可以通过点击题目上方《已通过》查看其他通过代码来学习。

题目内容

小红有一个长度为$n$的数组，他想要选择一个下标$i(1≤i<n)$，随后，将$a_i$及其左边元素全部染红，$a_i$右边的元素全部染蓝，使得红色元素的极差和蓝色元素的极差†的差的绝对值最小，请你直接输出这个值。

†:极差 是指数组中最大值和最小值的差。

输入描述

第一行输入一个整数$n(2≤n≤10^5)$代表数组的长度。

第二行$n$个整数$a_1,a_2,...,a_n(1≤a_i≤10^9)$代表数组的元素。

输出描述

在一行上输出一个正整数，表示红色元素的极差和蓝色元素的极差的差的绝对值的最小值。

样例1

输入

5
1 2 4 3 5

输出

1

说明

红色元素为$1,2,4$，极差为$4-1=3$;蓝色元素为$3,5$，极差为$5-3=2$，差的绝对值为$1$。