$$\color{Red}{货仓选址——两种语言}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

绝对值不等式

1. 基本思想
   对数组a排序，得到x序列数组
   然后求x使得Σ(0 - n-1)[xi - x]最小
   可以从两两分组的角度进行数形结合，显然应该是每组最中间的位置，如果是偶数点，就应该是中位数，如果是奇数点，就应该是中心点

2. 数学证明
   先对{xi}进行分组，d总=[|xn−x|+|x1−x|]+[|xn−1−x|+|x2−x|]+.....
   d总=[|xn−x|+|x1−x|]+[|xn−1−x|+|x2−x|]+.....
   对于每一组Min(|a−x|+|b−x|) = b−a
   Min(|a−x|+|b−x|)=b−a，
   则d总≥xn−x1+xn−1−x2+....d总≥xn−x1+xn−1−x2+....
   当且仅当x1≤x≤xnx1≤x≤xn，x2≤x≤xn−1x2≤x≤xn−1，...., xi≤x≤xjxi≤x≤xj时，等号成立
   因此上述结论得证

3. 相关题型

基本写法1 ——> 已知结论优化代码

拓展，此时代码中abs中写为a[i] - a[i // 2]也对，可以进行分组拆分证明
来自抽风大佬的 证明过程

java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int n, N = 100010;
    static int[] arr = new int[N];

    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(br.readLine());
        String[] s2 = br.readLine().split(" ");
        for (int i = 0; i < n; i++) arr[i] = Integer.parseInt(s2[i]);
        Arrays.sort(arr, 0, n);
        int res = 0;
        for (int i = 0; i < n; i++) {
            res += Math.abs(arr[i] - arr[n / 2]);
        }
        System.out.println(res);
    }
}

python

n = int(input())
a = [int(x) for x in input().split()]
a.sort()

res = 0
for i in range(n):
    res += abs(a[i] - a[n//2])

print(res)

写法2 已知过程模拟过程

java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int n, N = 100010;
    static int[] arr = new int[N];

    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(br.readLine());
        String[] s2 = br.readLine().split(" ");
        for (int i = 0; i < n; i++) arr[i] = Integer.parseInt(s2[i]);
        Arrays.sort(arr, 0, n);
        int res = 0;
        int i = 0, j = n - 1;
        while (i <= j){
            res += arr[j] - arr[i];
            i++;
            j--;
        }
        System.out.println(res);
    }
}

python

n = int(input())
a = [int(x) for x in input().split()]
a.sort()

res = 0
i = 0
j = n-1

while i <= j:
    res += a[j] - a[i]
    i += 1
    j -= 1
print(res)