【贪心】货仓选址

题目

104. 货仓选址 - AcWing题库

---

在一条数轴上有 $N$ 家商店，它们的坐标分别为 $A_1 \sim A_N$ 。

现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。

为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。

输入格式

第一行输入整数 $N$ 。

第二行 $N$ 个整数 $A_1 \sim A_N$ 。

输出格式

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

数据范围

$1 \le N \le 100000$ ,
$0 \le A_i \le 40000$

输入样例：

4
6 2 9 1

输出样例：

12

解题

方法一：贪心算法

思路

设货仓的位置为 $x$ ，那么货仓到每家商店的距离之和为：$sum = |A_1 - x| + |A_2 - x| + |A_3 - x| + \dots + |A_{N-1} - x| + |A_N - x|$ 。
把首位两项结合，整理一下：$sum = (|A_1 - x| + |A_N - x|) + (|A_2 - x| + |A_{N-1} - x|) + \dots + (|A_{\lfloor\frac{N}{2}\rfloor} - x| + |A_{\lfloor\frac{N}{2}\rfloor + 1} - x|)$ 。
观察发现，如果此时货仓在每一项的商店中间时，距离之和取得最小值：$sum = (A_N - A_1) + (A_{N - 1} - A_2) + \dots + (A_{\lfloor\frac{N}{2}\rfloor + 1} - A_{\lfloor\frac{N}{2}\rfloor})$。
此时货仓在中间的个商店之间（商店数量为偶数时）或在中间的商店上（商店数量为奇数时），也即中位数。

所以要取得最小距离之和应该把所有商店排序后使用双指针指向两端，然后向内收缩并把指向的两项做差累和为距离。

代码

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        int[] a = new int[n];
        for (int i = 0; i < n; ++i) {
            in.nextToken();
            a[i] = (int) in.nval;
        }
        Arrays.sort(a);
        long ans = 0L;
        for (int l = 0, r = n - 1; l < r; ++l, --r) ans += a[r] - a[l];
        System.out.println(ans);
    }
}