算法作业 _ 8_袁胜_2016M8009073008

Python

基本思路

采用贪婪算法。
不失一般性，设左侧为街道起点，右侧为街道终点，即 H[1] 在街道左侧。

• 首先在 H[1] 右侧 100 米处设立第一所邮局 P[1]。这样 H[1] 满足了100米内有邮局的条件。
• 沿H[1]向右考察其他房屋，如果距离 P[1] 在100米以内，则忽略；如果找到房屋 H[k]，距离 P[1]超过100米，则在 H[k] 右侧 100 米处设立邮局 P[2]。
• 重复上述过程，每遇到有不满足100米内有邮局条件的房屋，即在该房屋右侧100米处设立邮局。
• 直到考察到最后一所房屋 H[n]，如果 H[n] 不满足100米内有邮局的条件，即在 H[n] 所处位置设立邮局P[m]，算法结束。

伪码

Algorithm PostOffice(H[]):
  n <- Length(H);
  P[] <- 存储所有邮局位置的数组
  P[0] <- H[0] + 100;
  LastPost <- P[0];
  for (i in 1..n-1; j <- 0):
    if Abs(H[i] - LastPost) <= 100:
      continue;
    else:
      // 如果是最后一间房，邮局选址在当前房屋位置；
      // 否则向右100米。
      P[j] <- (i is n-1) ? H[i] : H[i] + 100;
      LastPost <- P[j];
      j++;
    end
  end
  m <- Length(P); // 记录邮局总数
  return P;
end

时间复杂度分析

算法只是循环遍历一遍所有的房屋，令考察房屋位置 H[k]是否满足100米内有邮局的过程复杂度为$O(1)$，则算法整体时间复杂度为$O(n)$， n为 H[] 的长度。