蓬莱山仙峰台题解

注:点击标题即可查看原题

NO.1 题意解析

在蓬莱山有 N个观景台,称为TP. 1 ,TP. 2,TP.3......TP.N ,观景台TP.i高度为h[i] 。还有 M条道路，每条道路连接两条不同的观景台。有一条道路j连接两个不同的观景台,分别为A和B，并且一个观景台可能有多条道路连接。若某个观景台满足下面的任意条件，我们则称它为​仙峰台： 1. 这个观景台比所有与他直接相连的观景台都要高。(这意味着不能相等) 2.没有任何一个观景台能够到达这个观景台(既没有任何一条路可以到达这里)

现在给你观景台和道路数据，请你算一下蓬莱山有多少个仙峰台。

输入描述: H M H1,H2,H3.....HN A1 B1 A2 B2 ..........

输出描述: 仙峰台的数量 注:为了方便理解,文字有所改动

NO.2 思路解析

首先可以看到,题目要我们求的是仙峰台的数量,基于仙峰台的条件,我们可以看出以下条件:这一个观景台一定是要比所有跟它相连的观景台要高的或者它独立存在,不和任何观景台相连,而且可能会有多条道路连接,所以很容易想到多种揭解法

在这里有两种思路,逻辑也有所不同,但相对于其它写法,这两种写法是更为简便的

解法一:可以先假设所有观景台都为仙峰台,通过遍历所有路径,一组一组的将A观景台和B观景台作比较,将高度低于其它的观景台的观景台排除,最终保留下来的就是仙峰台。这里可以不用特判是否独立存在的观景台,因为最开始已经假设所有的观景台都是仙峰台了,遍历时如果这个观景台是独立的,那么这个观景台便不会被遍历,也就自然不会被排除了。这是最简便也是最快和最容易理解的解法

解法二:这一种解法与第一种截然相反,做法是统计每种观景台大于其它观景台的次数和观景台出现的总次数。这种解法也相对易懂,统计出现的总次数就是指某个观景台连接其它观景台的总数量,如果都比和它相连的观景台高(也就是出现次数与大于其它观景塔台的次数相等)那么这个就一定是仙峰台。着一种方法也不用特判是否独立,因为独立意味着出现次数和比其它观景台大的次数都是0,会相等,也会被算进仙峰台中。

解法三:虽然这种解法最复杂,但是非常通用。两个观景台互相相连,就可以将数据存在数组当中,将同一个观景台的数据串联起来,统计完成之后,只需判断和这一个观景台是否比串联起来的观景台要高,如果是,那么这就是一个仙峰台,另外,如果这一个观景台没有和其它观景台相串联,那么这也是一个仙峰台。