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

这是一道经典的最优化问题，可以用贪心算法和动态规划算法来解决。下面分别介绍两种算法。

1. 贪心算法

贪心算法的思想是每一步都选择当前最优的解，最终得到全局最优的解。对于这道问题，我们可以分别确定两个邮局的位置，然后计算所有居民到这两个邮局的距离之和，最后选择最小的距离之和作为最终的解。

具体来说，我们可以枚举所有可能的邮局位置，计算每个居民到这两个邮局的距离之和，然后选取最小的距离之和作为最优解。由于邮局的位置有 n 种选择，因此时间复杂度为 O(n^3)。

2. 动态规划算法

动态规划算法的思想是将大问题分解为小问题，并记录中间结果，从而避免重复计算。对于这道问题，我们可以先将所有居民按照坐标值排序，然后考虑只建立一个邮局的情况，即所有居民到这个邮局的距离之和最小是多少。

假设我们在第 i 个居民处建立一个邮局，则第 j 个居民到这个邮局的距离为 |x[j] - x[i]|，其中 x[k] 表示第 k 个居民的坐标值。因此，对于一个给定的 i，我们可以计算出所有居民到这个邮局的距离之和。这可以通过动态规划来实现。

具体来说，我们可以定义一个二维数组 dp[i][j]，表示前 j 个居民中建立一个邮局在第 i 个居民处的最小距离和。对于任意的 i 和 j，有以下状态转移方程：

dp[i][j] = dp[i][j-1] + |x[j] - x[(i+j)/2]| - |x[j] - x[(i+j-1)/2]|

其中，|a-b| 表示 a 和 b 的差的绝对值。这个方程的意义是将第 j 个居民加入到第 i 个居民处建立的邮局中，同时将前 j-1 个居民已经建立的邮局向右移动一位。由于我们要计算的是最小距离和，因此需要在所有 dp[i][j] 中选择最小值。

最终的解可以通过枚举两个邮局的位置，将两个位置分别作为 i 来计算，然后将两个距离和相加，得到最小值。

算法的时间复杂度为 O(n^2)，空间复杂度也为 O(n^2)。