推 idiont: 大師 02/12 22:49
→ idiont: 想說既然是求最小 往反方向前進必然不是最佳解 就沒特別提 02/12 22:51
→ idiont: 但重看一次題敘後感覺我描述的不太正確 02/12 22:58
※ 引述《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：
------------------------------------
class Solution {
private long result;
public long minimumFuelCost(int[][] roads, int seats) {
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i <= roads.length; i++) {
graph.add(new ArrayList<>());
}
for (int[] road : roads) {
graph.get(road[0]).add(road[1]);
graph.get(road[1]).add(road[0]);
}
result = 0;
dfs(graph,0, -1, seats);
return result;
}
private long dfs(List<List<Integer>> graph, int curr, int prev, int
seats) {
int peopleCount = 1;
for (int edge : graph.get(curr)) {
if (edge == prev) continue;
long subPeople = dfs(graph, edge, curr, seats);
result += (subPeople + seats - 1) / seats;
peopleCount += subPeople;
}
return peopleCount;
}
}
------------------------------------
--
https://i.imgur.com/bFRiqA3.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.75.86 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1676209671.A.580.html