在一条直线公路旁有 n 户居民在居住，每个房子的位置用一个坐标值表示。 现在要在公路沿线建立两个邮局，使每个居民到邮局距离之和为最小，求两个邮 局的位置。例如，某个居民到两个邮局的距离分别为 12 和 19，则把较小的 12 作 为该居民到邮局的距离。采用分治法，用C语言编写代码，并给出注释。结果可输入居民点的坐标，输出邮局坐标

分治法求解最优邮局位置问题的思路是：先对居民的坐标进行排序，然后找到中间的坐标作为一个邮局的位置，将所有居民分为左右两部分，分别计算左右两边居民到该邮局的距离之和，然后递归求解左右两部分的最优邮局位置，取得到的距离之和最小的位置作为最终的解。下面是C语言代码实现：

#include <stdio.h>
#include <stdlib.h>

#define MAX_N 1000

int n; // 居民数量
int m; // 邮局数量
int a[MAX_N]; // 居民坐标数组
int d[MAX_N][MAX_N]; // 居民到邮局的距离

int cmp(const void* a, const void* b) {
    return *(int*)a - *(int*)b;
}

int dist(int x, int y) {
    // 计算两个居民的距离
    return abs(a[x] - a[y]);
}

int solve(int l, int r, int pos) {
    // 求解 [l, r] 区间内建立一个邮局的最小距离和
    int sum = 0;
    for (int i = l; i <= r; i++) {
        sum += dist(i, pos);
    }
    int ans = sum;
    for (int i = l; i < r; i++) {
        sum += dist(i, pos) - dist(i + 1, pos);
        if (sum < ans) {
            ans = sum;
        }
    }
    return ans;
}

int calc(int l, int r) {
    // 求解 [l, r] 区间内建立两个邮局的最小距离和
    if (l >= r) {
        return 0;
    }
    int mid = (l + r) / 2; // 中间坐标
    int sum = 0;
    for (int i = l; i <= r; i++) {
        sum += dist(i, mid);
    }
    int ans = sum + calc(l, mid - 1) + calc(mid + 1, r); // 求解左右两部分的距离和
    for (int i = l; i < mid; i++) {
        int tmp = solve(i, mid - 1, mid);
        ans = ans < tmp + calc(l, i - 1) + calc(i + 1, r) ? ans : tmp + calc(l, i - 1) + calc(i + 1, r); // 取最小的距离和
    }
    for (int i = mid + 1; i <= r; i++) {
        int tmp = solve(mid + 1, i, mid);
        ans = ans < tmp + calc(l, i - 1) + calc(i + 1, r) ? ans : tmp + calc(l, i - 1) + calc(i + 1, r); // 取最小的距离和
    }
    return ans;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    qsort(a, n, sizeof(int), cmp); // 对居民坐标进行排序
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            d[i][j] = solve(i, j, (i + j) / 2); // 预处理所有居民到邮局的距离
        }
    }
    int ans = calc(0, n - 1); // 求解最小距离和
    printf("邮局的位置为 %d 和 %d\n", a[(n - 1) / 2], a[n / 2]);
    return 0;
}

注：本题的时间复杂度为O(n^3)，可以通过一些优化来提高效率。