用java分治法解决邮局选址问题

邮局选址问题是指在一定范围内选取若干个点作为邮局，使得这些邮局到所有居民的距离之和最小。

使用分治法可以解决这个问题，具体步骤如下：

1. 将居民点按照横坐标排序。
2. 将整个区间分成两个子区间，分别对左右两个子区间递归求解。
3. 对于左右两个子区间，计算出中间位置的横坐标 mid，并将该点作为中间点，计算出左右两边到该点的所有居民的距离之和。
4. 比较左右两边的距离和，选择距离和较小的一边作为中间点的位置，并返回距离和最小的中间点位置和距离和。

Java代码实现如下：

public class MailboxLocation {
    private static int INF = 0x3f3f3f3f;

    public static int mailboxLocation(int[] a, int l, int r, int p) {
        if (l >= r) return INF;
        int mid = (l + r) >> 1;
        int dis = 0;
        for (int i = l; i <= r; i++) {
            dis += Math.abs(a[i] - a[mid]);
        }
        int ans = INF;
        if (mid > p) {
            ans = Math.min(ans, mailboxLocation(a, l, mid - 1, mid));
        }
        if (mid < p) {
            ans = Math.min(ans, mailboxLocation(a, mid + 1, r, mid));
        }
        return Math.min(dis, ans);
    }

    public static void main(String[] args) {
        int[] a = {1, 3, 5, 7, 9};
        int ans = mailboxLocation(a, 0, a.length - 1, -1);
        System.out.println(ans);
    }
}

此处我们假设所有居民点的纵坐标都相同，即只需要考虑横坐标距离。代码中的参数 p 表示上一次递归中选取的中间点位置，初始值为 -1。