java---贪心---货仓选址（每日一道算法2022.11.5）

题目：
在一条数轴上有 N 家商店，它们的坐标分别为 A1∼AN。
现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。
为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。

第一行输入整数 N。
第二行 N 个整数 A1∼AN。

输出一个整数，表示距离之和的最小值。

1 ≤ N ≤ 100000
0 ≤ Ai ≤ 40000

输入:
4
6 2 9 1
1
2
3

输出：
12
1
2

public class 货仓选址 {
    public static int N = 100010, n;
    public static int[] d = new int[N];

    public static void main(String[] args) {
        //读入
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        for (int i = 0; i<n; i++) d[i] = in.nextInt();

        //排序，方便之后找到中位数
        Arrays.sort(d, 0, n);

        //计算所有点到中位数的距离(因为根据推论得知，中位数即是货仓位置的最优解)
        int res = 0;
        for (int i = 0; i<n; i++) {
            res += Math.abs(d[i] - d[n/2]);		//这里是用每个点减去中位数，取绝对值就得到距离
        }

        System.out.println(res);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

思路：
中位数即为货仓位置的最优解

举个栗子：
现在在数轴上，有两个点a和b，我们想要取一个点x，使得从x到a和b的长度加起来最小
1.取a到b之间的任意点，2.取a左侧的点或者取b右侧的点
情况1，长度为：|a-x| + |b-x| = |a-b|
情况2，长度为：|a-x| + |b-x| > |a-b|
所以为了取得最优解，肯定是选择取a到b之间的点，也就是直接中位数即可

通过两个点的栗子，可以延伸到n个点，道理都是一样的，我们只需要将由小到大的点依次排序
让第1个点和第n个点对比，第2个点和第n-1个点对比…一直到中位数即可
(n为偶数取中间两个数的任意一个即可，为奇数的话就会有确定的中位数)

声明：
算法思路来源为y总，详细请见https://www.acwing.com/
本文仅用作学习记录和交流