思路：数学题

给定一个长度为$n$的数组$a$。求修改第$i$个元素为多少时，数组的的最小差异度会最小？

数组的最小差异度定义为：数组所有相邻元素差值的绝对值的和。

可以很容易发现，当修改第$1$个和第$n$个元素时，显然修改其为$a_2$和$a_{n-1}$最好。而对于其他元素，由于差异值的定义，可以令$a_i$为$a_{i-1}$与$a_{i+1}$之间任意一值，这样，$a_i$与$a_{i-1}、a_{i+1}$的差异值可以用如下公式计算$a_{i+1}-a_i+a_i-a_{i-1}=a_{i+1}-a_{i-1}$(如果$a_{i-1}\gt a_{i+1}$，交换它们的值即可)。

如果令$a_i\lt a_{i-1}$或$a_i\gt a_{i+1}$，那么他们的差异值为$a_{i+1}-a_i$或$a_i-a_{i-1}$，由于大小关系，一定比上面的值大。

代码

C++

AC

#include <iostream>
#include <cstdio>
using namespace std;
#define ll long long

const int maxn = 1e5 + 10;
int n;
ll a[maxn];

// 计算两个数的绝对差
ll Abs(ll x, ll y) {
    return x > y ? x - y : y - x;
}

int main() {
    std::ios::sync_with_stdio(false);
    cin >> n; // 输入整数 n，表示数组长度
    for (int i = 1; i <= n; ++i) {
        cin >> a[i]; // 输入数组元素
    }
    ll res = 0; // 初始化结果变量

    // 计算数组中相邻元素的绝对差之和
    for (int i = 2; i <= n; ++i) {
        res += Abs(a[i], a[i - 1]);
    }

    for (int i = 1; i <= n; ++i) {
        if (i == 1) {
            // 对于第一个元素，减去其与第二个元素的绝对差
            printf("%lld ", res - Abs(a[1], a[2]));
        } else if (i == n) {
            // 对于最后一个元素，减去其与倒数第二个元素的绝对差
            printf("%lld ", res - Abs(a[n], a[n - 1]));
        } else {
            // 对于中间元素，计算删除该元素后的绝对差之和
            printf("%lld ", res - Abs(a[i], a[i - 1]) - Abs(a[i], a[i + 1]) + Abs(a[i - 1], a[i+1]));
        }
    }

    return 0;
}

python

# 计算两个数的绝对差
def Abs(x, y):
    return abs(x - y)

n = int(input())  # 输入整数 n，表示数组长度
a = list(map(int, input().split()))  # 输入数组元素

res = 0  # 初始化结果变量

# 计算数组中相邻元素的绝对差之和
for i in range(1, n):
    res += Abs(a[i], a[i - 1])

for i in range(n):
    if i == 0:
        # 对于第一个元素，减去其与第二个元素的绝对差
        print(res - Abs(a[0], a[1]), end=' ')
    elif i == n - 1:
        # 对于最后一个元素，减去其与倒数第二个元素的绝对差
        print(res - Abs(a[n - 1], a[n - 2]), end=' ')
    else:
        # 对于中间元素，计算删除该元素后的绝对差之和
        print(res - Abs(a[i], a[i - 1]) - Abs(a[i], a[i + 1]) + Abs(a[i - 1], a[i + 1]), end=' ')

Java

import java.util.*;

public class Main {
    public static void solve() {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();  // 输入整数 n，表示字符串数量
        HashSet<String> st = new HashSet<>();  // 创建一个集合 st，用于去重
        ArrayList<String> v = new ArrayList<>();  // 创建一个列表 v，用于存储去重后的字符串

        // 循环读取输入的字符串
        for (int i = 0; i < n; i++) {
            String s = scanner.next();
            if (st.contains(s)) {
                continue;  // 如果字符串已存在于集合 st 中，跳过重复的字符串
            }
            v.add(s);  // 否则将字符串加入列表 v
            st.add(s);  // 并将字符串添加到集合 st 中，以便去重
        }

        int m = v.size();  // 获取去重后的字符串数量
        String[] w = new String[m];  // 创建一个长度为 m 的数组 w，用于存储处理后的日期时间字符串

        // 遍历去重后的字符串列表
        for (int i = 0; i < m; i++) {
            String t = v.get(i);
            int pos = t.indexOf('-');  // 找到日期部分的分隔符位置
            String u = t.substring(pos - 4, pos + 6) + t.substring(pos + 7, pos + 15);  // 拼接年月日:2019-01-01 时分秒:09:00:01
            w[i] = u;  // 将处理后的字符串存入数组 w
        }

        Integer[] p = new Integer[m];
        for (int i = 0; i < m; i++) {
            p[i] = i;  // 创建一个排序索引数组 p，初始为 [0, 1, 2, ..., m-1]
        }

        // 使用 Comparator 进行排序，首先按照日期时间字符串排序，然后按照字符串长度排序，最后按照字符串内容排序
        Arrays.sort(p, (a, b) -> {
            if (!w[a].equals(w[b])) {
                return w[a].compareTo(w[b]);
            } else if (v.get(a).length() != v.get(b).length()) {
                return Integer.compare(v.get(a).length(), v.get(b).length());
            } else {
                return v.get(a).compareTo(v.get(b));
            }
        });

        // 遍历排序后的索引数组 p，按照排序顺序输出字符串
        for (int i = 0; i < m; i++) {
            System.out.println(v.get(p[i]));
        }
    }

    public static void main(String[] args) {
        int T = 1;
        while (T-- > 0) {
            solve();  // 调用解决问题的函数
        }
    }
}

题目描述

小红从一个神秘人那里获得了一个长度为$N$的数组。神秘人告诉小红，小红可以修改数组的一个元素，来改变数组的最小差异度。小红想知道，当他修改第$i$个元素为多少时，数组的的最小差异度会最小？

数组的最小差异度定义为：数组所有相邻元素差值的绝对值的和。

输入描述

第一行为一个整数$N \leq 10^5$，代表数组的长度

第二行为$n$个正整数$a_i(a_i\le 10^9)$，代表数组元素。

输出描述

$N$个整数，代表修改第$i$个元素能够达到的最小差异度。

样例

输入

4
1 2 1 2

输出

2 1 1 2