※ 引述《idiont (supertroller)》之铭言:
: 2477. Minimum Fuel Cost to Report to the Capital
: 给一棵 tree,有 n 个点代表 n 个城市,
: 每座城市都有车可以通往其他相邻的城市,一台车最多可以一次载 seats 个人,
: 现在每座城市都有一个人要到 0 号城市,求最少需要几台车。
思路:
1.这题关键点是必须注意到一个规律:所有的车子都是从最外面往中心点(0号城市)移动
若你要从中心点往外移动的话因为要往返的关系所以会消耗两倍的油,必不是最佳解。
2.在一的前提之下,所有最外边的城市都往中心点方向移动,例如:下列红色的点往上移
0
|
1
/ | \
2 3 4
2,3,4城市各使用一台车,共消耗3公升的油前进到1城市,此时1城市共有4个人,若要
继续往市中心移动的话,需要消耗的油量为:(城市当前人数/座位大小)向上取整
上述的关系式不断从最外圈的城市往市中心递回求可以求得解答。
3.当前城市人数等于 1 + 子树节点数量,我们只需要用DFS找出所有点的子树数量就可以
求得解了。
JavaCode: