题2:公交换乘 【题目描述】 著名旅游城市 B B B 市为了鼓励大家采用公共交通方式出行,推出了一种地铁换乘公交车的优惠方案: 1、在搭乘一次地铁后可以获得一张优惠票,有效期为 45 分钟,在有效期内可以消耗这张优惠票,免费搭乘一次票价不超过地铁票价的公交车。在有效期内指开始乘公交车的时间与开始乘地铁的时间之差小于等于 45 分钟,即: t b u s − t s u b w a y
题目大意 给出一颗N个点的无根树,定义两点间距离为当其中一点为另一点祖先时为1,否则为2,求最短距离和 solution 先考虑确定了根的情况 设 s z [ i ] sz[i] sz[i]为以 i i i为根的子树大小(包括 i i i) 则在以 f a [ i ] fa[i] fa[i]为根的子树中,以 i i i为根的子树中每一个都要向外连 s z [ f a [ i ] ] −
题目 给定一个一维数组,其中每一个元素表示相邻公交站之间的距离,比如有四个公交站A,B,C,D,对应的距离数组为,1,2,3,4,如下图示 给定目标站X和Y,求他们之间最短的距离 解题 遍历一次整个数组,将不再此区间内的和在此区间内的分别算一个综合,取其最小值 public class DistanceBetweenBusStopTest {public static void m