java写代码在一条直线公路旁有n户居民在居住，每个房子的位置用一个坐标值表示。现在要在公路沿线建立两个邮局，使每个居民到邮局距离之和为最小，求两个邮局的位置。例如，某个居民到两个邮局的距离分别为12和19，则把较小的12作为该居民到邮局的距离。。

这是一个经典的最优化问题，可以使用贪心算法和动态规划算法来解决。

一、贪心算法：

1. 对居民的位置进行排序。
2. 从前往后遍历每个居民，每次选择在当前居民的左侧或右侧建立一个邮局，使得左右两侧居民到该邮局的距离之和最小。
3. 重复步骤2，直到建立了两个邮局。

代码实现：

public static int[] buildPostOffice(int[] houses, int num) {
    Arrays.sort(houses);
    int[] res = new int[2];
    int len = houses.length;
    int[][] dp = new int[len + 1][num + 1];
    for (int i = 1; i <= len; i++) {
        Arrays.fill(dp[i], Integer.MAX_VALUE);
        dp[i][1] = getDistance(houses, 0, i - 1);
    }
    for (int i = 2; i <= num; i++) {
        for (int j = i; j <= len; j++) {
            for (int k = i - 1; k < j; k++) {
                dp[j][i] = Math.min(dp[j][i], dp[k][i - 1] + getDistance(houses, k, j - 1));
            }
        }
    }
    int minDist = dp[len][num];
    int cnt = num;
    for (int i = len; i >= num; i--) {
        if (dp[i][cnt] == minDist) {
            cnt--;
            res[cnt] = houses[i - 1];
        }
    }
    return res;
}

private static int getDistance(int[] houses, int start, int end) {
    int mid = (start + end) / 2;
    int dist = 0;
    for (int i = start; i <= end; i++) {
        dist += Math.abs(houses[i] - houses[mid]);
    }
    return dist;
}

二、动态规划算法：

1. 对居民的位置进行排序。
2. 使用动态规划求解，dp[i][j]表示前i个居民建立j个邮局的最小距离和。
3. 初始状态为dp[i][1] = getDistance(houses, 0, i-1)，表示只建立一个邮局时的距离和。
4. 状态转移方程为dp[i][j] = min(dp[k][j-1] + getDistance(houses, k, i-1))，表示前k个居民建立j-1个邮局，第j个邮局建在k到i-1的位置中的最小距离和。
5. 最终答案为dp[len][num]，表示前len个居民建立num个邮局的最小距离和。

代码实现：

public static int[] buildPostOffice(int[] houses, int num) {
    Arrays.sort(houses);
    int[] res = new int[2];
    int len = houses.length;
    int[][] dp = new int[len + 1][num + 1];
    for (int i = 1; i <= len; i++) {
        Arrays.fill(dp[i], Integer.MAX_VALUE);
        dp[i][1] = getDistance(houses, 0, i - 1);
    }
    for (int i = 2; i <= num; i++) {
        for (int j = i; j <= len; j++) {
            for (int k = i - 1; k < j; k++) {
                dp[j][i] = Math.min(dp[j][i], dp[k][i - 1] + getDistance(houses, k, j - 1));
            }
        }
    }
    int minDist = dp[len][num];
    int cnt = num;
    for (int i = len; i >= num; i--) {
        if (dp[i][cnt] == minDist) {
            cnt--;
            res[cnt] = houses[i - 1];
        }
    }
    return res;
}

private static int getDistance(int[] houses, int start, int end) {
    int mid = (start + end) / 2;
    int dist = 0;
    for (int i = start; i <= end; i++) {
        dist += Math.abs(houses[i] - houses[mid]);
    }
    return dist;
}