[关闭]
@Pigmon 2016-04-29T06:11:55.000000Z 字数 658 阅读 125

算法作业 _ 8_袁胜_2016M8009073008

Python


基本思路

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

伪码

  1. Algorithm PostOffice(H[]):
  2. n <- Length(H);
  3. P[] <- 存储所有邮局位置的数组
  4. P[0] <- H[0] + 100;
  5. LastPost <- P[0];
  6. for (i in 1..n-1; j <- 0):
  7. if Abs(H[i] - LastPost) <= 100:
  8. continue;
  9. else:
  10. // 如果是最后一间房,邮局选址在当前房屋位置;
  11. // 否则向右100米。
  12. P[j] <- (i is n-1) ? H[i] : H[i] + 100;
  13. LastPost <- P[j];
  14. j++;
  15. end
  16. end
  17. m <- Length(P); // 记录邮局总数
  18. return P;
  19. end

时间复杂度分析

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

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注