一个简单的贪心算法问题

        什么是贪心算法？先抄一段定义吧~

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。贪心算法有很多经典的应用，比如霍夫曼编码（Huffman Coding）、Prim 和 Kruskal 最小生成树算法、还有 Dijkstra 单源最短路径算法等等。

        这里简单介绍一个用贪心算法解决邮局位置的问题。

题目是这样的：

在一条街上有 n 所房子，H[i] (1 ≤ i ≤ n) 是第 i 所房子离街道起点处的距离（以米为单位），假定 H[1] < H[2] < · · · < H[n]。目前该街道上还没有一所邮局，现计划新建若干所邮局，使得每所房子到最近的邮局距离在 100 米以内。试设计一个时间复杂度为 O(n) 的算法，计算出新建邮局的位置，即每所新建邮局离街道起点处的距离 P[j](1 ≤ j ≤ m)，同时确保新建邮局个数 m 最小。

贪心算法解题思路：

1. 确定第一所邮局位置应为 P[1] = H[1] + 100；
2. 从 H[2] 开始检查每个 H[i]，若 H[i] > P[m] + 100，则 m 增 1，P[m] = H[i] + 100，否则继续检查下一所房子位置 H[i + 1]；
3. 如果 P[m] > H[n]，则令 P[m] = H[n]

伪代码：

PostOfficePos(H[], n) {
    P[1] = H[1] + 100; 
    m = 1;
    for i = 2 to n {
        if H[i] > P[m] + 100 then
        m = m + 1; 
        P[m] = H[i] + 100; 
    }
    if P[m] > H[n] then P[m] = H[n];
    return (P, m);  
}