PAT 解题报告 1072. Gas Station (30)

1072. Gas Station 题目描述:

A gas station has to be built at such a location that the minimum distance between the station and any of the residential housing is as far away as possible.1 However it must guarantee that all the houses are in its service range.

Now given the map of the city and several candidate locations for the gas station, you are supposed to give the best recommendation. If there are more than one solution, output the one with the smallest average distance to all the houses. If such a solution is still not unique, output the one with the smallest index number.

题目要求是说要在住宅区建设加油站, 这个加油站的要求是1. 这个加油站到所有的房子的最小距离尽可能的大 2. 这个加油站到每个房子的距离都要在预先设定的某个服务范围内. 现在给出所有房子和加油站的图, 求出最优的那个加油站, 或者输出没有这样的解.

1072. Gas Station 算法分析:

这个题目应该不难, 注意下下文提到的两点即可. 所以算法就是: 遍历所有的加油站, 每次遍历, 都把当前的加油站当成是起点, 利用最短路径算法(迪杰斯特拉), 计算出从这个当前加油站到每个房子的最短距离(可以利用其它加油站作为中间点), 这些最短距离就被定义成了加油站到每个房子的距离, 那么针对这些距离求得最小值以及验证每个距离是不是在服务范围内, 每个加油站都可以拿到这个最小距离一起求得平均距离, 按照要求输出最短距离最大的那个加油站, 如果存在多个, 那么输出平均距离最小的那个.

1072. Gas Station 注意点:

这个题目有两点模糊的地方: (1) 加油站到房子的距离的定义? 虽然没有明确给出, 但是仔细想想, 似乎也只能定义成图上的两点之间的最短路径的长度 (2) 在计算最短路径的时候其他加油站可以作为中间点参与最短路径的计算. 以上两点已经通过OJ的测试得到验证.

 

(全文完,原创文章,转载时请注明作者和出处)


(转载本站文章请注明作者和出处 烟客旅人 sigmainfy — http://www.sigmainfy.com,请勿用于任何商业用途)

Written on December 23, 2013