步行道是树,先从大门 0 定根,得到每个投放点往里走的下一段。
关键在于状态要带上「挪车用过没有」:
(u, used):人在投放点 u,且已找物业挪过的次数为 used∈{0,1}width[u] > width[v],推车直接开过去,used 不变;否则只有 used=0 时才能挪一次车走到 (v,1)晚饭高峰,外卖小哥从小区大门(编号 0)推车往里送餐。大门、楼栋门洞、单元口这些投放点共 n 个,编号 0..n−1。点与点之间的步行道由 links 给出,保证构成一棵以大门为根的树——从大门走进去不会绕圈。
每个投放点有通道净宽 width[i](越大越宽)。推车只能开进比当前更窄的下一段路,否则会刮蹭绿化带:
本单配送可以找物业挪一次挡路的共享单车(整趟只能用一次,也可以不用),从而无视一次宽度限制,强行通过一条边。
请返回:从大门 0 出发,最多能到达多少个投放点(含大门自己)。
请实现:
maxDropoffReach(n: int, links: int[][], width: int[]) -> int
三行:
nlinks,形如 [[0, 1], [0, 2]],共 n−1 条边,保证成树width,长度为 $n`约束:
links.length =n−1,0≤u,v<n,无自环一个整数:最多能到达的投放点数。
输入:
5
[[0, 1], [0, 2], [1, 3], [1, 4]]
[10, 6, 8, 1, 9]
输出:
5
说明:路够窄时可以走 0→1→3、0→2。边 1→4 因 6>9 会卡住,但可以挪一次共享单车通过,五个点都能送到。
输入:
3
[[0, 1], [1, 2]]
[1, 2, 3]
输出:
2
说明:通道越走越宽,只能挪一次,最多走到 1,到不了 2。
输入:
1
[]
[7]
输出:
1
说明:小区里只有大门这一个投放点。
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.