题目是一个墨西哥朋友给我的，所以题解得是全英文。

语法错误，算法伪证，术语错误等都可以挑刺。

先谢谢各位巨佬了 orz orz

题面：

Let us consider a long , quiet country road with houses scattered very sparsely along it .

Further , let us suppose that the residents of all these houses are avid cel phone users . You want to place cel phone base stations at certain points along the road , so that every house is within four miles of one of the base stations .

Give an efficient algorithm that achieves this goal , using as few base stations as possible . Prove correctness .

我的题解：

Above all, the distance between the adjacent houses may be very far, which makes the road too long to deal with. However, it doesn't matter how far it is as long as the distance is greater than $8$ miles, because the stations between the two house can't reach both of them anyhow.

Thus, if it is greater than $8$ , we can assume that it is exactly $9$ .

For every house seated at $a_i$ , there are $9$ points where a station can reach it. These points are at $\{a_{i}-4,a_{i}-3,...,a_{i}+4\}$ . We can assume that the house contribute $1$ coverage to these $9$ points

Let $c[i]$ be the contributions that the $i$-th point received from nearby houses. By using a difference array, we can calculate $c$ with the time complexity of $O(n)$.

To cover as many houses as possible with one station, we should place the station at the point whose $c[i]$ is as great as possible. So we do that in the decreasing order of $c$ until all the houses are covered.

(Proof: if we place a station at where $c[i]$ is smaller, it can't cover more houses than we did just now. So the needed stations can't be fewer. The answer must be inferior to that we had just now. )

To avoid covering a house unnecessarily repeatedly, we should mark the houses which have been covered. So every time we place a station at $i$ , we should mark the range $[i-4,i+4]$ as a no-station area.

(Proof: if we place a station outside the area, it can cover more houses than inside the area, and the house covered in the range won't be lost. )

To do this efficiently, we should push the $<c[i],i>$ pairs into a heap in the decreasing order of $c[i]$ . Every time we grab the top of the heap, pop it out, check if it's in a no-station area, place the station and mark the range if not.

To mark and check the range more efficiently, we can build a segment tree with tags, or just a binary indexed tree can tackle everthing.

The total time complexity is no more than $O(n\log n)$ .