试题四(共15分)

阅读以下说明和图，填补流程图中的空缺，将解答填入答题纸的对应栏内。

[说明]

在一条农村公路的一边稀疏地分布着房子，其分布如图 4-1 所示。某电信公司需要在某些位置放置蜂窝电话基站，由于基站的覆盖范围是6公里，因此必须使得每栋房子到某个基站的直线距离不超过6公里。为简化问题，假设所有房子在同一直线上，并且基站沿该直线放置。现采用贪心策略实现用尽可能少的基站覆盖所有的房子。

实现贪心算法的流程如图4-2所示，请填充其中空白并计算该算法的时间复杂度，其中：

1．d[i](1≤ i ≤ N)表示第i个房子到公路A端的距离，N 表示房子的总数，房子的编号按照房子到公路A 端的距离从小到大进行编号。

2．s[k]表示第k（k ≥1）个基站到公路A 端的距离，算法结束后k的值为基站的总数。 

该算法的时间复杂度为 （5） 。

[答案讨论]

[1]  [2]  [3]  [4]  [5]  [6]  [7]  [8]  [9]  [10]  [11]  [12]  [13]